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
113 votes
Accepted

Problems Between P and NPC

82 votes

Complexity of the simplex algorithm

54 votes

Algorithms from the Book

44 votes
Accepted

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

43 votes

What papers should everyone read?

36 votes

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

29 votes
Accepted

Great algorithms, machine learning and no linear algebra

27 votes

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

24 votes
Accepted

Grid $k$-coloring without monochromatic rectangles

23 votes

What kind of mathematical background is needed for complexity theory?

21 votes

Major unsolved problems in theoretical computer science?

19 votes

Open problems on the frontiers of TCS

18 votes

Why is CNF used for SAT and not DNF?

18 votes

Why go to theoretical computer science/research?

16 votes
Accepted

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

16 votes

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

16 votes
Accepted

Algorithm for optimizing decision trees

14 votes
Accepted

Proper PAC learning of 2-DNF under uniform distribution

13 votes
Accepted

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

13 votes

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

13 votes

Where and how did computers help prove a theorem?

13 votes

Grid $k$-coloring without monochromatic rectangles

13 votes

The Warren Buffett Problem

12 votes
Accepted

Learning with "taciturn" oracles

12 votes

Are there any open problems left about DFAs?

11 votes
Accepted

Lower bounds for learning in the membership query and counterexample model

11 votes

A lottery that you can be convinced that it is fair

11 votes
Accepted

complexity of randomized gossiping

11 votes

Reference for fundamental theorem on tree rotations

11 votes

What are the best current lower bounds on 3SAT?