Lev Reyzin's user avatar
Lev Reyzin's user avatar
Lev Reyzin's user avatar
Lev Reyzin
Moderator
  • Member for 13 years, 1 month
  • Last seen more than a month ago
141 votes
30 answers
25k views

Problems Between P and NPC

102 votes
15 answers
11k views

A simple decision problem whose decidability is not known

46 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
501 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
367 views

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

12 votes
1 answer
873 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
208 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
168 views

Cryptography with very small keys