Stack Exchange

Robin Kothari

http://www.robinkothari.com

I am a theoretical computer scientist. My research interests include quantum algorithms and complexity theory.

top accounts reputation activity subscriptions
Top Questions
65 votes

Problems that can be used to show polynomial-time hardness results

cc.complexity-theory lower-bounds conditional-results asked Sep 14, 2010 at 2:56
cstheory.stackexchange.com

62 votes

Open problems on the frontiers of TCS

big-list open-problem asked Sep 6, 2010 at 4:38
cstheory.stackexchange.com

45 votes

Subscripts for primed variables

math-mode subscripts asked Sep 18, 2010 at 13:29
tex.stackexchange.com

38 votes

What is the oldest open problem in TCS?

soft-question open-problem ho.history-overview asked Oct 3, 2010 at 5:17
cstheory.stackexchange.com

25 votes

Formula size lower bounds for AC0 functions

cc.complexity-theory lower-bounds circuit-complexity formulas asked Jun 28, 2011 at 22:59
cstheory.stackexchange.com

25 votes

Approximate degree of $\textrm{AC}^0$

cc.complexity-theory reference-request circuit-complexity polynomials asked Jul 18, 2012 at 16:10
cstheory.stackexchange.com

23 votes

Do all complexity classes have a leaf language characterization?

cc.complexity-theory complexity-classes asked Aug 30, 2010 at 3:15
cstheory.stackexchange.com

22 votes

Lower bounds for constant-depth formulae?

cc.complexity-theory circuit-complexity lower-bounds asked Aug 17, 2010 at 5:34
cstheory.stackexchange.com

21 votes

What is the most general structure on which matrix product verification can be done in $O(n^2)$ time?

ds.algorithms linear-algebra matrix-product asked Apr 7, 2011 at 18:56
cstheory.stackexchange.com

21 votes

Spelling to pronunciation

pronunciation spelling phonetics asked Nov 3, 2011 at 22:24
german.stackexchange.com

1 2 3

Top Answers
52
What papers should everyone read?
cstheory.stackexchange.com

40
Do any quantum algorithms improve on classical SAT?
cstheory.stackexchange.com

34
Semantic vs. Syntactic Complexity Classes
cstheory.stackexchange.com

32
Funny TCS-related papers etc?
cstheory.stackexchange.com

32
What are the recent TCS books whose drafts are available online?
cstheory.stackexchange.com

26
What Lecture Notes Should Everyone Read?
cstheory.stackexchange.com

25
Major unsolved problems in theoretical computer science?
cstheory.stackexchange.com

25
What is the big version of NC?
cstheory.stackexchange.com

25
What are the recent TCS books whose drafts are available online?
cstheory.stackexchange.com

24
Small steps for better TCS conferences?
cstheory.stackexchange.com

22
What hierarchies and/or hierarchy theorems do you know?
cstheory.stackexchange.com

21
Is 0-1 programming with constant number of constraints polynomially solvable?
cstheory.stackexchange.com

21
Dinner-table description of theoretical computer science?
cstheory.stackexchange.com

20
Is PARITY in QAC_0 (if that even makes sense)
cstheory.stackexchange.com

20
Is $PH \subseteq PP$?
cstheory.stackexchange.com

20
What's the "smallest" complexity class for which a superlinear circuit bound is known?
cstheory.stackexchange.com

19
Is there a Quantum equivalent of the Time hierarchy theorem ?
cstheory.stackexchange.com

18
A problem that is in PSPACE but not known to be in PH?
cstheory.stackexchange.com

18
what is easy for minor-excluded graphs?
cstheory.stackexchange.com

18
Parity and circuit complexity
cstheory.stackexchange.com

17
What are good references to understanding the proof of the PCP theorem?
cstheory.stackexchange.com

17
Can knowing ahead the length of 3-SAT instance really help?
mathoverflow.net

17
Best Upper Bounds on SAT
cstheory.stackexchange.com

17
Lower bounds for constant-depth formulae?
cstheory.stackexchange.com

16
How hard is it to count the number of factors of an integer?
cstheory.stackexchange.com

16
Oracle results on P vs BPP
cstheory.stackexchange.com

16
Is BQP equal to BPP with access to an Abelian hidden subgroup oracle?
cstheory.stackexchange.com

16
Is there a syntactic characterization for BPP, BQP, or QMA?
mathoverflow.net

16
Which $AC^0$ problems are not "truly feasible"?
cstheory.stackexchange.com

16
Is relativization well-defined?
cstheory.stackexchange.com

1 2 3 4