Skip to main content
Lev Reyzin's user avatar
Lev Reyzin's user avatar
Lev Reyzin's user avatar
Lev Reyzin
Moderator
  • Member for 13 years, 11 months
  • Last seen more than a month ago
141 votes
30 answers
25k views

Problems Between P and NPC

104 votes
15 answers
11k views

A simple decision problem whose decidability is not known

48 votes
8 answers
21k views

Complexity of Finding the Eigendecomposition of a Matrix

37 votes
9 answers
3k views

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

36 votes
8 answers
11k views

Alan Turing's Contributions to Computer Science

22 votes
1 answer
506 views

Natural, untestable graph properties

17 votes
3 answers
1k views

Properties of Random Directed Graphs with Fixed Out-Degree

17 votes
3 answers
728 views

Randomize or Not?

13 votes
2 answers
399 views

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

12 votes
1 answer
892 views

The Cost of an Equivalence Query for DFA

12 votes
3 answers
350 views

Complexity of Localization in Wireless Networks

4 votes
1 answer
209 views

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

3 votes
2 answers
200 views

Nonregular Languages in Sublogarithmic Space

2 votes
1 answer
171 views

Cryptography with very small keys