User Robin Kothari

9 votes

How to know if X and Y have coauthored?

answered Oct 31, 2010 at 6:11

9 votes

What is the difference between non-determinism and randomness?

answered Aug 26, 2010 at 15:54

9 votes

Kolmogorov complexity applications in computational complexity

answered Sep 8, 2010 at 2:13

9 votes

Beginner's Guide to Derandomization

answered Sep 8, 2010 at 20:13

9 votes

Open problems on the frontiers of TCS

answered Sep 8, 2010 at 20:30

9 votes

Introduction to spectral graph theory

answered Sep 10, 2010 at 21:18

8 votes

Accepted

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

answered Sep 9, 2010 at 15:29

8 votes

Truly random number generator: Turing computable?

answered Sep 14, 2010 at 2:23

8 votes

A relaxed Steiner Tree Problem

answered Sep 7, 2010 at 18:18

8 votes

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

answered Aug 28, 2010 at 6:14

8 votes

Accepted

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

answered May 6, 2011 at 0:47

8 votes

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

answered Jun 30, 2011 at 18:36

8 votes

Real world applications of quantum computing (except for security)

answered Dec 8, 2012 at 0:30

8 votes

Accepted

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

answered Aug 15, 2012 at 22:12

8 votes

Accepted

Quantum algorithms for determining whether two sets intersect

answered Mar 24, 2012 at 14:20

8 votes

Models of computation strictly between classical and quantum in terms of query complexity

answered Nov 24, 2011 at 21:47

8 votes

Accepted

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

answered Jun 11, 2013 at 17:04

8 votes

Runtime of Grover's algorithm

answered Dec 29, 2015 at 2:39

7 votes

Accepted

Las Vegas vs Monte Carlo randomized decision tree complexity

answered Jun 21, 2015 at 20:02

7 votes

Accepted

Maximize quadratic function subject to linear constraints

answered May 22, 2013 at 0:52

7 votes

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

answered Feb 17, 2013 at 3:55

7 votes

Definition of matrix-multiplication exponent $\omega$

answered Nov 29, 2011 at 23:16

7 votes

Using decision version of TSP to solve optimization version

answered Sep 8, 2010 at 15:09

7 votes

Accepted

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

answered Sep 18, 2010 at 19:08

7 votes

Global properties of hereditary classes?

answered Sep 16, 2010 at 17:54

6 votes

Accepted

Is there an oracle separating Parity-P from PSPACE?

answered Jul 11, 2014 at 7:51

6 votes

Does approximation degree of AND depend on error?

answered Jun 9, 2015 at 21:02

6 votes

Accepted

Was this complexity measure studied before?

answered Jan 11, 2017 at 4:33

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

Stack Exchange Network

108 Answers

How to know if X and Y have coauthored?

What is the difference between non-determinism and randomness?

Kolmogorov complexity applications in computational complexity

Beginner's Guide to Derandomization

Open problems on the frontiers of TCS

Introduction to spectral graph theory

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

Truly random number generator: Turing computable?

A relaxed Steiner Tree Problem

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

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

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

Real world applications of quantum computing (except for security)

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

Quantum algorithms for determining whether two sets intersect

Models of computation strictly between classical and quantum in terms of query complexity

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

Runtime of Grover's algorithm

Las Vegas vs Monte Carlo randomized decision tree complexity

Maximize quadratic function subject to linear constraints

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

Definition of matrix-multiplication exponent $\omega$

Using decision version of TSP to solve optimization version

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

Global properties of hereditary classes?

Is there an oracle separating Parity-P from PSPACE?

Does approximation degree of AND depend on error?

Was this complexity measure studied before?

Separation of AM and SZK

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