User Robin Kothari

2 votes

The complexity of LH with constant gap

answered Mar 20, 2021 at 1:46

3 votes

Quantum evasiveness conjecture?

answered May 5, 2020 at 18:23

52 votes

What papers should everyone read?

answered Sep 12, 2010 at 2:26

22 votes

What hierarchies and/or hierarchy theorems do you know?

answered Jul 11, 2011 at 3:17

6 votes

Accepted

Separation of AM and SZK

answered Jul 14, 2019 at 4:16

5 votes

Lower bound on alternations needed in $BQP$ versus $PH$ result?

answered May 17, 2019 at 16:01

3 votes

Representing OR with polynomials

answered May 27, 2018 at 17:27

2 votes

About the sign-rank of the Minsky-Pappert function

answered Aug 3, 2017 at 3:30

32 votes

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

answered Dec 5, 2010 at 6:40

6 votes

Accepted

Was this complexity measure studied before?

answered Jan 11, 2017 at 4:33

40 votes

Do any quantum algorithms improve on classical SAT?

answered Aug 17, 2016 at 20:34

8 votes

Runtime of Grover's algorithm

answered Dec 29, 2015 at 2:39

3 votes

On optimality of Grover algorithm with high success probability

answered Dec 22, 2015 at 13:09

7 votes

Accepted

Las Vegas vs Monte Carlo randomized decision tree complexity

answered Jun 21, 2015 at 20:02

13 votes

Open problems on the frontiers of TCS

answered Sep 8, 2010 at 4:37

6 votes

Does approximation degree of AND depend on error?

answered Jun 9, 2015 at 21:02

1 vote

One sided approximation degree

answered May 17, 2015 at 23:51

10 votes

Accepted

Deterministic communication complexity vs partition number

answered Apr 9, 2015 at 15:23

14 votes

Accepted

To which complexity class does this language belong?

answered Mar 12, 2015 at 12:12

5 votes

Accepted

How well can an arbitrary (unknown) quantum state be imperfectly cloned?

answered Mar 12, 2015 at 11:10

3 votes

Bounding the gap between quantum and deterministic query complexity

answered Aug 13, 2014 at 19:17

6 votes

Accepted

Is there an oracle separating Parity-P from PSPACE?

answered Jul 11, 2014 at 7:51

11 votes

Journals with quick reviewing

answered Jun 12, 2012 at 16:00

14 votes

Good text on introduction to circuit complexity

answered May 11, 2014 at 15:08

13 votes

Accepted

Hardness of quantum circuit equivalence?

answered May 10, 2014 at 23:08

11 votes

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

answered May 9, 2014 at 17:52

16 votes

Accepted

Is relativization well-defined?

answered Mar 18, 2014 at 15:29

17 votes

Lower bounds for constant-depth formulae?

answered Jan 21, 2014 at 16:03

11 votes

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

answered Dec 7, 2013 at 15:35

8 votes

Accepted

What is the minimum required depth of reductions for NP-hardness of SAT?

answered Jun 11, 2013 at 17:04

Stack Exchange Network

108 Answers

The complexity of LH with constant gap

Quantum evasiveness conjecture?

What papers should everyone read?

What hierarchies and/or hierarchy theorems do you know?

Separation of AM and SZK

Lower bound on alternations needed in $BQP$ versus $PH$ result?

Representing OR with polynomials

About the sign-rank of the Minsky-Pappert function

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

Was this complexity measure studied before?

Do any quantum algorithms improve on classical SAT?

Runtime of Grover's algorithm

On optimality of Grover algorithm with high success probability

Las Vegas vs Monte Carlo randomized decision tree complexity

Open problems on the frontiers of TCS

Does approximation degree of AND depend on error?

One sided approximation degree

Deterministic communication complexity vs partition number

To which complexity class does this language belong?

How well can an arbitrary (unknown) quantum state be imperfectly cloned?

Bounding the gap between quantum and deterministic query complexity

Is there an oracle separating Parity-P from PSPACE?

Journals with quick reviewing

Good text on introduction to circuit complexity

Hardness of quantum circuit equivalence?

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

Is relativization well-defined?

Lower bounds for constant-depth formulae?

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

What is the minimum required depth of reductions for NP-hardness of SAT?