User Lev Reyzin

113 votes

Accepted

Problems Between P and NPC

answered Aug 18, 2010 at 4:09

81 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

17 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

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 problems without efficient algorithms, where existence theorems have proved such algorithms must exist?

answered Feb 7, 2011 at 21:56

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

What machine learning classifiers are the most parallelizeable?

answered Jan 25, 2011 at 21:48

11 votes

Accepted

Clustering formalizations other than K-means for separable data

answered Nov 15, 2010 at 23:47

11 votes

Accepted

complexity of randomized gossiping

answered Oct 25, 2010 at 14:48

Stack Exchange Network

95 Answers

Problems Between P and NPC

Complexity of the simplex algorithm

Algorithms from the Book

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

What papers should everyone read?

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

Great algorithms, machine learning and no linear algebra

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

Grid $k$-coloring without monochromatic rectangles

What kind of mathematical background is needed for complexity theory?

Major unsolved problems in theoretical computer science?

Open problems on the frontiers of TCS

Why is CNF used for SAT and not DNF?

Why go to theoretical computer science/research?

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

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

Algorithm for optimizing decision trees

Proper PAC learning of 2-DNF under uniform distribution

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

Where and how did computers help prove a theorem?

Grid $k$-coloring without monochromatic rectangles

The Warren Buffett Problem

Learning with "taciturn" oracles

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

Are there any open problems left about DFAs?

Lower bounds for learning in the membership query and counterexample model

A lottery that you can be convinced that it is fair

What machine learning classifiers are the most parallelizeable?

Clustering formalizations other than K-means for separable data

complexity of randomized gossiping