User Lev Reyzin - Theoretical Computer Science Stack Exchange

Lev Reyzin

Moderator

Member for 13 years, 1 month
Last seen more than a month ago

Twitter
levreyzin.com
Chicago, IL

14 Questions

Score Activity Newest Views

141 votes

30 answers

25k views

Problems Between P and NPC

asked Aug 17, 2010 at 2:07

102 votes

15 answers

11k views

A simple decision problem whose decidability is not known

asked Sep 4, 2013 at 2:24

46 votes

8 answers

20k views

Complexity of Finding the Eigendecomposition of a Matrix

asked Nov 1, 2010 at 13:28

37 votes

9 answers

2k views

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

asked Aug 18, 2010 at 18:14

35 votes

8 answers

11k views

Alan Turing's Contributions to Computer Science

asked Jun 24, 2012 at 2:47

22 votes

1 answer

501 views

Natural, untestable graph properties

asked Sep 25, 2012 at 1:33

17 votes

3 answers

1k views

Properties of Random Directed Graphs with Fixed Out-Degree

asked Sep 13, 2010 at 15:19

17 votes

3 answers

721 views

Randomize or Not?

asked Oct 15, 2010 at 22:11

13 votes

2 answers

367 views

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

asked Feb 6, 2011 at 19:36

12 votes

1 answer

873 views

The Cost of an Equivalence Query for DFA

asked Jan 3, 2013 at 22:44

12 votes

3 answers

349 views

Complexity of Localization in Wireless Networks

asked Aug 19, 2010 at 15:35

4 votes

1 answer

208 views

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

asked Feb 9, 2015 at 20:33

3 votes

2 answers

197 views

Nonregular Languages in Sublogarithmic Space

asked Nov 30, 2013 at 18:38

2 votes

1 answer

168 views

Cryptography with very small keys

asked Feb 12, 2015 at 22:04