User Robin Kothari

52 votes

What papers should everyone read?

answered Sep 12, 2010 at 2:26

42 votes

Do any quantum algorithms improve on classical SAT?

answered Aug 17, 2016 at 20:34

36 votes

Accepted

Semantic vs. Syntactic Complexity Classes

answered Sep 13, 2010 at 3:54

32 votes

Funny TCS-related papers etc?

answered Nov 18, 2010 at 6:46

32 votes

What are the recent TCS books whose drafts are available online?

answered Dec 5, 2010 at 6:40

26 votes

What Lecture Notes Should Everyone Read?

answered Jan 5, 2011 at 4:47

25 votes

What are the recent TCS books whose drafts are available online?

answered Dec 5, 2010 at 6:32

25 votes

What is the big version of NC?

answered May 27, 2011 at 21:11

25 votes

Major unsolved problems in theoretical computer science?

answered Aug 18, 2010 at 5:03

24 votes

Small steps for better TCS conferences?

answered May 8, 2011 at 12:15

22 votes

What hierarchies and/or hierarchy theorems do you know?

answered Jul 11, 2011 at 3:17

21 votes

Accepted

Is 0-1 programming with constant number of constraints polynomially solvable?

answered May 22, 2012 at 22:51

21 votes

Dinner-table description of theoretical computer science?

answered Sep 20, 2010 at 2:46

20 votes

Is $PH \subseteq PP$?

answered Nov 23, 2010 at 21:38

20 votes

Is PARITY in QAC_0 (if that even makes sense)

answered Feb 24, 2011 at 21:20

20 votes

What's the "smallest" complexity class for which a superlinear circuit bound is known?

answered Dec 5, 2010 at 18:39

19 votes

Is there a Quantum equivalent of the Time hierarchy theorem ?

answered Jan 21, 2011 at 16:14

18 votes

Parity and circuit complexity

answered Dec 7, 2010 at 1:01

18 votes

what is easy for minor-excluded graphs?

answered Oct 22, 2010 at 22:53

18 votes

A problem that is in PSPACE but not known to be in PH?

answered May 9, 2011 at 1:32

18 votes

Best Upper Bounds on SAT

answered Sep 7, 2010 at 19:37

17 votes

What are good references to understanding the proof of the PCP theorem?

answered Aug 17, 2010 at 4:12

17 votes

Is BQP equal to BPP with access to an Abelian hidden subgroup oracle?

answered Sep 14, 2010 at 15:40

17 votes

Oracle results on P vs BPP

answered Aug 21, 2012 at 2:53

17 votes

Lower bounds for constant-depth formulae?

answered Jan 21, 2014 at 16:03

16 votes

Accepted

Is relativization well-defined?

answered Mar 18, 2014 at 15:29

16 votes

Accepted

How hard is it to count the number of factors of an integer?

answered Aug 11, 2012 at 2:42

16 votes

Intractability of NP-complete problems as a principle of physics?

answered Sep 18, 2010 at 5:58

16 votes

Accepted

Which $AC^0$ problems are not "truly feasible"?

answered Sep 2, 2010 at 0:13

15 votes

Accepted

References on Circuit Lower Bounds

answered Sep 28, 2010 at 22:13

Stack Exchange Network

108 Answers

What papers should everyone read?

Do any quantum algorithms improve on classical SAT?

Semantic vs. Syntactic Complexity Classes

Funny TCS-related papers etc?

What are the recent TCS books whose drafts are available online?

What Lecture Notes Should Everyone Read?

What are the recent TCS books whose drafts are available online?

What is the big version of NC?

Major unsolved problems in theoretical computer science?

Small steps for better TCS conferences?

What hierarchies and/or hierarchy theorems do you know?

Is 0-1 programming with constant number of constraints polynomially solvable?

Dinner-table description of theoretical computer science?

Is $PH \subseteq PP$?

Is PARITY in QAC_0 (if that even makes sense)

What's the "smallest" complexity class for which a superlinear circuit bound is known?

Is there a Quantum equivalent of the Time hierarchy theorem ?

Parity and circuit complexity

what is easy for minor-excluded graphs?

A problem that is in PSPACE but not known to be in PH?

Best Upper Bounds on SAT

What are good references to understanding the proof of the PCP theorem?

Is BQP equal to BPP with access to an Abelian hidden subgroup oracle?

Oracle results on P vs BPP

Lower bounds for constant-depth formulae?

Is relativization well-defined?

How hard is it to count the number of factors of an integer?

Intractability of NP-complete problems as a principle of physics?

Which $AC^0$ problems are not "truly feasible"?

References on Circuit Lower Bounds