Stack Exchange

Robin Kothari

Waterloo, Canada

robinkothari.com

I am a PhD student in CS at the University of Waterloo. My research interests include quantum algorithms and complexity theory.

top accounts reputation activity favorites subscriptions
Top Questions
45 votes

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

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

38 votes

Open problems on the frontiers of TCS

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

29 votes

What is the oldest open problem in TCS?

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

21 votes

Formula size lower bounds for AC0 functions

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

17 votes

Most efficient way to convert an $\text{AC}^0$ circuit to a circuit (of any depth) with gate fanout 1

cc.complexity-theory lower-bounds circuit-complexity asked Aug 8 '11 at 23:11
cstheory.stackexchange.com

17 votes

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

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

17 votes

Spelling to pronunciation

pronunciation spelling phonetics asked Nov 3 '11 at 22:24
german.stackexchange.com

16 votes

Problems between NC and P: How many have been resolved from this list?

cc.complexity-theory open-problem circuit-complexity asked Sep 15 '10 at 2:44
cstheory.stackexchange.com

15 votes

Do all complexity classes have a leaf language characterization?

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

14 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 '11 at 18:56
cstheory.stackexchange.com

1 2

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

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

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

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

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

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

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

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

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

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

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

18
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

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

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

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

15
Estimating Average in Polynomial Time
cstheory.stackexchange.com

14
Which $AC^0$ problems are not “truly feasible” ?
cstheory.stackexchange.com

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

14
References on Circuit Lower Bounds
cstheory.stackexchange.com

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

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

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

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

12
Parity and circuit complexity
cstheory.stackexchange.com

12
Citation showing minors are topological minors for subcubic graphs
cstheory.stackexchange.com

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

11
Intractability of NP-complete problems as a principle of physics?
cstheory.stackexchange.com

11
Does there exist a quantum algorithm ala Deutsch's algorithm that computs AND instead of XOR?
cstheory.stackexchange.com

10
Understanding QMA
cstheory.stackexchange.com

1 2 3