Open Problem Garden
Help
About
Contact
login/create account
Home
»
Subject
»
Theoretical Comp. Sci.
Complexity
Title
Author(s)
Imp.¹
Rec.²
Subtopic
Posted by
Unconditional derandomization of Arthur-Merlin games
Shaltiel
;
Umans
✭✭✭
0
Derandomization
ormeir
Subset-sums equality (pigeonhole version)
✭✭✭
0
mdevos
Refuting random 3SAT-instances on $O(n)$ clauses (weak form)
Feige
✭✭✭
0
Hardness of Approximation
cwenner
P vs. PSPACE
Folklore
✭✭✭
0
cwenner
P vs. BPP
Folklore
✭✭✭
0
Derandomization
Charles R Great...
One-way functions exist
✭✭✭✭
0
porton
Linear-size circuits for stable $0,1 < 2$ sorting?
Regan
✭✭
1
KWRegan
Discrete Logarithm Problem
✭✭✭
0
cplxphil
Complexity of square-root sum
Goemans
✭✭
0
abie
Navigate
Subject
Algebra
(7)
Analysis
(5)
Combinatorics
(35)
Geometry
(29)
Graph Theory
(228)
Group Theory
(5)
Logic
(10)
Number Theory
(49)
PDEs
(0)
Probability
(1)
Theoretical Comp. Sci.
(13)
Algorithms
(2)
Coding Theory
(1)
Complexity
(9)
Derandomization
(2)
Hardness Amplification
(0)
Hardness of Approximation
(1)
Interactive Proofs
(0)
PCP
(0)
Cryptography
(0)
Topology
(40)
Unsorted
(1)
Author index
Keyword index
more
Recent Activity
Chords of longest cycles
Do any three longest paths in a connected graph have a vertex in common?
Chromatic number of $\frac{3}{3}$-power of graph
3-Edge-Coloring Conjecture
r-regular graphs are not uniquely hamiltonian.
more