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

95 Answers

Score Activity Newest

113 votes

Accepted

Problems Between P and NPC

answered Aug 18, 2010 at 4:09

82 votes

Complexity of the simplex algorithm

answered Oct 22, 2010 at 3:20

54 votes

Algorithms from the Book

answered Aug 17, 2010 at 20:06

44 votes

Accepted

Is finding the minimum regular expression an NP-complete problem?

answered Oct 1, 2010 at 21:21

43 votes

What papers should everyone read?

answered Sep 12, 2010 at 2:18

36 votes

What is the enlightenment I'm supposed to attain after studying finite automata?

answered Dec 23, 2012 at 4:23

29 votes

Accepted

Great algorithms, machine learning and no linear algebra

answered Nov 15, 2010 at 16:28

27 votes

Can one return to a TCS research job after an excursion to a non-research industry job?

answered Mar 5, 2013 at 3:15

24 votes

Accepted

Grid $k$-coloring without monochromatic rectangles

answered Feb 8, 2012 at 14:32

23 votes

What kind of mathematical background is needed for complexity theory?

answered Nov 1, 2010 at 0:50

21 votes

Major unsolved problems in theoretical computer science?

answered Aug 17, 2010 at 20:40

19 votes

Open problems on the frontiers of TCS

answered Sep 8, 2010 at 23:12

18 votes

Why is CNF used for SAT and not DNF?

answered Sep 17, 2010 at 15:48

18 votes

Why go to theoretical computer science/research?

answered Sep 22, 2010 at 13:57

16 votes

Accepted

Natural problems in $NP \cap coNP$ not in $UP \cap coUP$?

answered Aug 19, 2010 at 21:11

16 votes

Is a PhD in TCS the best way towards achieving a career in industrial research?

answered Mar 6, 2011 at 15:47

16 votes

Accepted

Algorithm for optimizing decision trees

answered Aug 25, 2011 at 0:11

14 votes

Accepted

Proper PAC learning of 2-DNF under uniform distribution

answered Jan 20, 2012 at 5:47

13 votes

Accepted

Does an infinitely long tape make any difference when proving theorems about Turing Machines?

answered Jan 11, 2011 at 23:19

13 votes

Are there problems without efficient algorithms, where existence theorems have proved such algorithms must exist?

answered Feb 7, 2011 at 21:56

13 votes

Where and how did computers help prove a theorem?

answered Aug 18, 2010 at 4:38

13 votes

Grid $k$-coloring without monochromatic rectangles

answered Sep 27, 2010 at 13:38

13 votes

The Warren Buffett Problem

answered Oct 22, 2010 at 20:44

12 votes

Accepted

Learning with "taciturn" oracles

answered Oct 26, 2010 at 13:19

12 votes

Are there any open problems left about DFAs?

answered May 13, 2014 at 20:16

11 votes

Accepted

Lower bounds for learning in the membership query and counterexample model

answered Apr 3, 2012 at 5:37

11 votes

A lottery that you can be convinced that it is fair

answered Jun 15, 2012 at 18:21

11 votes

Accepted

complexity of randomized gossiping

answered Oct 25, 2010 at 14:48

11 votes

Reference for fundamental theorem on tree rotations

answered Sep 23, 2010 at 13:52

11 votes

What are the best current lower bounds on 3SAT?

answered Aug 17, 2010 at 5:38

1