User Lev Reyzin - Theoretical Computer Science Stack Exchange

Lev Reyzin

Moderator

Member for 12 years, 10 months
Last seen this week

Twitter
levreyzin.com
Chicago, IL

14 Questions

Score Activity Newest Views

141 votes

30 answers

24k 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

45 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

500 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

359 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

869 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

205 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

165 views

Cryptography with very small keys

asked Feb 12, 2015 at 22:04