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
5 votes
Accepted

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

5 votes
Accepted

Finding all solutions by Grover search(not superposition)

5 votes
Accepted

Are provable quantum speed-ups possible for classes larger than NP?

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

Bounding the gap between quantum and deterministic query complexity

3 votes

On optimality of Grover algorithm with high success probability

3 votes

Representing OR with polynomials

3 votes

Quantum evasiveness conjecture?

2 votes

The complexity of LH with constant gap

2 votes

About the sign-rank of the Minsky-Pappert function

2 votes

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

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