User Robin Kothari

15 votes

Accepted

Estimating Average in Polynomial Time

answered Oct 2, 2010 at 16:56

14 votes

Why do we consider log-space as a model of efficient computation (instead of polylog-space) ?

answered Dec 2, 2010 at 5:04

14 votes

Good text on introduction to circuit complexity

answered May 11, 2014 at 15:08

14 votes

Accepted

To which complexity class does this language belong?

answered Mar 12, 2015 at 12:12

14 votes

How difficult is it to use the Mulmuley-Sohoni GCT approach to show known complexity separations?

answered Apr 24, 2013 at 18:28

13 votes

Accepted

Hardness of quantum circuit equivalence?

answered May 10, 2014 at 23:08

13 votes

Parameterized complexity from P to NP-hard and back again

answered Dec 2, 2010 at 19:30

13 votes

Accepted

Is the Witness Size of Membership for Every NP Language Already Known?

answered Oct 18, 2010 at 4:30

13 votes

Open problems on the frontiers of TCS

answered Sep 8, 2010 at 4:37

13 votes

Accepted

Citation showing minors are topological minors for subcubic graphs

answered Jul 11, 2011 at 14:34

13 votes

P with integer factorization oracle

answered Feb 8, 2011 at 4:58

12 votes

Applications of representation theory of the symmetric group

answered Sep 23, 2012 at 13:01

12 votes

NC = P consequences?

answered Sep 24, 2010 at 18:27

12 votes

Parameterized complexity from P to NP-hard and back again

answered Dec 3, 2010 at 4:52

12 votes

Accepted

Is Parity-P contained in PP?

answered Mar 24, 2013 at 3:29

12 votes

Accepted

Quantum PAC learning

answered Dec 8, 2012 at 6:51

11 votes

In what class are randomized algorithms that err with exactly 25% chance?

answered Dec 7, 2013 at 15:35

11 votes

Is $\mathsf{DTIME}(n^{O(\log n)})$ an interesting complexity class?

answered May 9, 2014 at 17:52

11 votes

Understanding QMA

answered Sep 18, 2010 at 21:24

11 votes

Accepted

Are there any classes of functions which require provably different resources to compute versus computing their inverse?

answered Sep 17, 2010 at 2:52

11 votes

What evidence is there that $coRP \neq NP$?

answered Aug 21, 2010 at 5:34

11 votes

Journals with quick reviewing

answered Jun 12, 2012 at 16:00

11 votes

Accepted

Does there exist a quantum algorithm ala Deutsch's algorithm that computs AND instead of XOR?

answered Oct 27, 2011 at 19:22

10 votes

Problems outside of P that are not P-hard

answered Sep 1, 2011 at 14:38

10 votes

Accepted

Hardest optimization problems in NC

answered Jun 3, 2012 at 18:51

10 votes

Is there a natural problem on the naturals that is NP-complete?

answered Oct 30, 2012 at 19:21

10 votes

Accepted

Trade off between time and query complexity

answered Jul 22, 2011 at 22:16

10 votes

Accepted

Deterministic communication complexity vs partition number

answered Apr 9, 2015 at 15:23

9 votes

Complexity class of phase information in Gauss sum

answered Jul 24, 2011 at 15:25

9 votes

Accepted

Is there a well-known nontrivial subset of NP for which it is known that it is a proper subset?

answered Mar 16, 2011 at 13:57

Stack Exchange Network

108 Answers

Estimating Average in Polynomial Time

Why do we consider log-space as a model of efficient computation (instead of polylog-space) ?

Good text on introduction to circuit complexity

To which complexity class does this language belong?

How difficult is it to use the Mulmuley-Sohoni GCT approach to show known complexity separations?

Hardness of quantum circuit equivalence?

Parameterized complexity from P to NP-hard and back again

Is the Witness Size of Membership for Every NP Language Already Known?

Open problems on the frontiers of TCS

Citation showing minors are topological minors for subcubic graphs

P with integer factorization oracle

Applications of representation theory of the symmetric group

NC = P consequences?

Parameterized complexity from P to NP-hard and back again

Is Parity-P contained in PP?

Quantum PAC learning

In what class are randomized algorithms that err with exactly 25% chance?

Is $\mathsf{DTIME}(n^{O(\log n)})$ an interesting complexity class?

Understanding QMA

Are there any classes of functions which require provably different resources to compute versus computing their inverse?

What evidence is there that $coRP \neq NP$?

Journals with quick reviewing

Does there exist a quantum algorithm ala Deutsch's algorithm that computs AND instead of XOR?

Problems outside of P that are not P-hard

Hardest optimization problems in NC

Is there a natural problem on the naturals that is NP-complete?

Trade off between time and query complexity

Deterministic communication complexity vs partition number

Complexity class of phase information in Gauss sum

Is there a well-known nontrivial subset of NP for which it is known that it is a proper subset?