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

Complexity class of phase information in Gauss sum

9 votes
Accepted

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

9 votes
Accepted

How efficiently can a 1-sparse Hamiltonian be simulated (quantum mechanically)?

9 votes

How to know if X and Y have coauthored?

9 votes

What is the difference between non-determinism and randomness?

9 votes

Kolmogorov complexity applications in computational complexity

9 votes

Beginner's Guide to Derandomization

9 votes

Open problems on the frontiers of TCS

9 votes
Accepted

Comparing $\mathbf{NP}$ and $\mathbf{E}$

9 votes

Introduction to spectral graph theory

8 votes

A relaxed Steiner Tree Problem

8 votes

Do many-one reductions and Turing reductions define the same class NPC

8 votes

Truly random number generator: Turing computable?

8 votes

Why does the Complexity Class PostBQP makes proving PP greater than or equal to QMA easier?

8 votes
Accepted

Quantum algorithms for determining whether two sets intersect

8 votes
Accepted

Can quantum algorithms with exponential speed-up be rederived using span-programs?

8 votes

Runtime of Grover's algorithm

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

7 votes

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

7 votes
Accepted

Las Vegas vs Monte Carlo randomized decision tree complexity

7 votes

Definition of matrix-multiplication exponent $\omega$

7 votes

Global properties of hereditary classes?

7 votes
Accepted

How can one construct a densest graph with no k-clique?

7 votes

Using decision version of TSP to solve optimization version

6 votes

Does approximation degree of AND depend on error?

6 votes
Accepted

Was this complexity measure studied before?

6 votes
Accepted

Separation of AM and SZK

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?