Lev Reyzin's user avatar
Lev Reyzin's user avatar
Lev Reyzin's user avatar
Lev Reyzin
Moderator
  • Member for 12 years, 10 months
  • Last seen this week
141 votes
30 answers
24k views

Problems Between P and NPC

102 votes
15 answers
11k views

A simple decision problem whose decidability is not known

45 votes
8 answers
20k views

Complexity of Finding the Eigendecomposition of a Matrix

37 votes
9 answers
2k views

Surprising Results in Complexity (Not on the Complexity Blog List)

35 votes
8 answers
11k views

Alan Turing's Contributions to Computer Science

22 votes
1 answer
500 views

Natural, untestable graph properties

17 votes
3 answers
1k views

Properties of Random Directed Graphs with Fixed Out-Degree

17 votes
3 answers
721 views

Randomize or Not?

13 votes
2 answers
359 views

Any Hypothesis Classes Other than Parity in Noisy PAC but not in SQ?

12 votes
1 answer
869 views

The Cost of an Equivalence Query for DFA

12 votes
3 answers
349 views

Complexity of Localization in Wireless Networks

4 votes
1 answer
205 views

Cryptographic systems that don't leak linear combinations of encrypted bits

3 votes
2 answers
197 views

Nonregular Languages in Sublogarithmic Space

2 votes
1 answer
165 views

Cryptography with very small keys