Theoretical Computer Science

Title	Author(s)	Imp.¹	Rec.²	Topic » Subtopic	Posted by
Sums of independent random variables with unbounded variance	Feige	✭✭	0		cwenner
P vs. NP	Cook; Levin	✭✭✭✭	0	Algorithms	zitterbewegung
Exponential Algorithms for Knapsack	Lipton	✭✭	1	Algorithms	dick lipton
The robustness of the tensor product	Ben-Sasson; Sudan	✭✭✭	0	Coding Theory	ormeir
Subset-sums equality (pigeonhole version)		✭✭✭	0	Complexity	mdevos
Complexity of square-root sum	Goemans	✭✭	0	Complexity	abie
Linear-size circuits for stable $0,1 < 2$ sorting?	Regan	✭✭	1	Complexity	KWRegan
Discrete Logarithm Problem		✭✭✭	0	Complexity	cplxphil
P vs. PSPACE	Folklore	✭✭✭	0	Complexity	cwenner
One-way functions exist		✭✭✭✭	0	Complexity	porton
Unconditional derandomization of Arthur-Merlin games	Shaltiel; Umans	✭✭✭	0	Complexity » Derandomization	ormeir
P vs. BPP	Folklore	✭✭✭	0	Complexity » Derandomization	Charles R Great...
Refuting random 3SAT-instances on $O(n)$ clauses (weak form)	Feige	✭✭✭	0	Complexity » Hardness of Approximation	cwenner

Open Problem Garden