user avatar
user avatar
user avatar
Andy Drucker
  • Member for 11 years, 10 months
  • Last seen more than a month ago
34 votes

What kind of mathematical background is needed for complexity theory?

28 votes

Why does randomness have stronger effect on reductions than on algorithms?

23 votes
Accepted

Examples where the uniqueness of the solution makes it easier to find

21 votes

Is optimally solving the n×n×n Rubik's Cube NP-hard?

20 votes

The cozy neighborhoods of "P" and of "NP-hard"

18 votes
Accepted

If P = BQP, does this imply that PSPACE (= IP) = AM?

17 votes
Accepted

Lower bounds on Gaussian complexity

14 votes

DFA intersection in subquadratic space?

14 votes

Natural problems in $NP \cap coNP$ not in $UP \cap coUP$?

14 votes

Hardness of noisy Boolean functions

14 votes
Accepted

Above #P and counting search problems

11 votes
Accepted

Smallest Boolean circuit to generate a language

11 votes

The cozy neighborhoods of "P" and of "NP-hard"

10 votes

Stochastic version of a strongly NP-Complete problem

10 votes

Are there known to exist functions with the following direct-sum property?

9 votes

Reduction SAT to a problem on a planar graph with as few vertices as possible

9 votes

What is the complexity of the fastest method of k-coloring any graph?

8 votes

Computing any information about Max-3SAT

8 votes

Evidence that PPAD is hard?

8 votes

Fast convolution over small finite fields

7 votes
Accepted

Algorithm to Determine if (Union of Cartesian Products of Subsets) equals (Cartesian Product of Full Sets)

7 votes
Accepted

How hard is it to count the number of local optima for a problem in PLS?

6 votes
Accepted

Two Variants of NP

6 votes
Accepted

Which results in complexity theory make essential use of uniformity?

5 votes
Accepted

Subset $k$-product

4 votes

grover's algorithm

2 votes
Accepted

On Random Self-reducible properties

2 votes
Accepted

Comparison between the maximum clique and maximum biclique problem

2 votes
Accepted

research on systematically attacking multiple instances of undecidable problems

1 vote

The complexity of recognizing optimal set systems for the V-C dimension