Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more
Robin Kothari's user avatar
Robin Kothari's user avatar
Robin Kothari's user avatar
Robin Kothari
  • Member for 13 years, 9 months
  • Last seen this week
6 votes
Accepted

Is there an oracle separating Parity-P from PSPACE?

5 votes
Accepted

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

5 votes

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

5 votes
Accepted

Delegating all of the work to the prover in $\mathcal{MA}$ protocols

4 votes

Consequences of Unique Games being a NPI problem

3 votes

Major conjectures used to prove complexity lower bounds?

3 votes

Complexity class separation in the presence of relativization barriers

3 votes

Representing OR with polynomials

3 votes

Quantum evasiveness conjecture?

3 votes

On optimality of Grover algorithm with high success probability

3 votes

Bounding the gap between quantum and deterministic query complexity

2 votes

Is there some mathematical closed form (or somewhat tight asymptotic one) for "Google Eggs Puzzle"?

2 votes

About the sign-rank of the Minsky-Pappert function

2 votes

The complexity of LH with constant gap

2 votes

Two Variants of NP

1 vote

Hamiltonicity of k-regular graphs

1 vote

Major conjectures used to prove complexity lower bounds?

1 vote

One sided approximation degree

1 2 3
4