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
Linear-size circuits for stable $0,1 < 2$ sorting?
Regan
✭✭
1
KWRegan
Complexity of square-root sum
Goemans
✭✭
0
abie
P vs. PSPACE
Folklore
✭✭✭
0
cwenner
P vs. BPP
Folklore
✭✭✭
0
Derandomization
Charles R Great...
Refuting random 3SAT-instances on $O(n)$ clauses (weak form)
Feige
✭✭✭
0
Hardness of Approximation
cwenner
Subset-sums equality (pigeonhole version)
✭✭✭
0
mdevos
Discrete Logarithm Problem
✭✭✭
0
cplxphil
One-way functions exist
✭✭✭✭
0
porton
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