Robin Kothari's user avatar
Robin Kothari's user avatar
Robin Kothari's user avatar
Robin Kothari
  • Member for 12 years, 1 month
  • Last seen more than a week ago
52 votes

What papers should everyone read?

39 votes

Do any quantum algorithms improve on classical SAT?

33 votes
Accepted

Semantic vs. Syntactic Complexity Classes

32 votes

Funny TCS-related papers etc?

32 votes

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

26 votes

What Lecture Notes Should Everyone Read?

25 votes

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

25 votes

Major unsolved problems in theoretical computer science?

24 votes

Small steps for better TCS conferences?

22 votes

What is the big version of NC?

22 votes

What hierarchies and/or hierarchy theorems do you know?

21 votes

Dinner-table description of theoretical computer science?

20 votes

Is $PH \subseteq PP$?

20 votes

Is PARITY in QAC_0 (if that even makes sense)

20 votes

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

20 votes
Accepted

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

19 votes

Is there a Quantum equivalent of the Time hierarchy theorem ?

18 votes

what is easy for minor-excluded graphs?

18 votes

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

17 votes

Parity and circuit complexity

17 votes

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

17 votes

Best Upper Bounds on SAT

17 votes

Lower bounds for constant-depth formulae?

16 votes
Accepted

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

16 votes

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

16 votes
Accepted

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

15 votes

Oracle results on P vs BPP

15 votes

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

15 votes
Accepted

References on Circuit Lower Bounds

15 votes
Accepted

Estimating Average in Polynomial Time