Robin Kothari's user avatar
Robin Kothari's user avatar
Robin Kothari's user avatar
Robin Kothari
  • Member for 13 years, 3 months
  • Last seen this week
2 votes

The complexity of LH with constant gap

3 votes

Quantum evasiveness conjecture?

6 votes
Accepted

Separation of AM and SZK

5 votes

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

3 votes

Representing OR with polynomials

2 votes

About the sign-rank of the Minsky-Pappert function

6 votes
Accepted

Was this complexity measure studied before?

40 votes

Do any quantum algorithms improve on classical SAT?

8 votes

Runtime of Grover's algorithm

3 votes

On optimality of Grover algorithm with high success probability

7 votes
Accepted

Las Vegas vs Monte Carlo randomized decision tree complexity

6 votes

Does approximation degree of AND depend on error?

1 vote

One sided approximation degree

10 votes
Accepted

Deterministic communication complexity vs partition number

14 votes
Accepted

To which complexity class does this language belong?

5 votes
Accepted

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

3 votes

Bounding the gap between quantum and deterministic query complexity

6 votes
Accepted

Is there an oracle separating Parity-P from PSPACE?

14 votes

Good text on introduction to circuit complexity

13 votes
Accepted

Hardness of quantum circuit equivalence?

11 votes

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

16 votes
Accepted

Is relativization well-defined?

17 votes

Lower bounds for constant-depth formulae?

11 votes

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

8 votes
Accepted

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

7 votes
Accepted

Maximize quadratic function subject to linear constraints

14 votes

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

12 votes
Accepted

Is Parity-P contained in PP?

5 votes
Accepted

Finding all solutions by Grover search(not superposition)

7 votes

Are there any problems whose best known algorithm has run time $O\left(\frac{f(n)}{\log n}\right)$