Stack Exchange

Andy Drucker

Princeton, NJ

http://people.csail.mit.edu/andyd/home.html

Postdoc at IAS. My research focus is computational complexity.

top accounts reputation activity favorites subscriptions
Top Questions
Top Answers
32
What kind of mathematical background is needed for complexity theory?
cstheory.stackexchange.com

28
Why does randomness have stronger effect on reductions than on algorithms?
cstheory.stackexchange.com

22
Examples where the uniqueness of the solution makes it easier to find
cstheory.stackexchange.com

21
Is optimally solving the n×n×n Rubik's Cube NP-hard?
cstheory.stackexchange.com

19
The cozy neighborhoods of “P” and of “NP-hard”
cstheory.stackexchange.com

18
If P = BQP, does this imply that PSPACE (= IP) = AM?
cstheory.stackexchange.com

17
Lower bounds on Gaussian complexity
cstheory.stackexchange.com

15
DFA intersection in subquadratic space?
cstheory.stackexchange.com

14
Hardness of noisy Boolean functions
cstheory.stackexchange.com

14
Above #P and counting search problems
cstheory.stackexchange.com

13
Natural problems in $NP \cap coNP$ not in $UP \cap coUP$?
cstheory.stackexchange.com

11
Smallest Boolean circuit to generate a language
cstheory.stackexchange.com

10
Are there known to exist functions with the following direct-sum property?
cstheory.stackexchange.com

10
The cozy neighborhoods of “P” and of “NP-hard”
cstheory.stackexchange.com

9
Stochastic version of a strongly NP-Complete problem
cstheory.stackexchange.com

9
Reduction SAT to a problem on a planar graph with as few vertices as possible
cstheory.stackexchange.com

9
What is the complexity of the fastest method of k-coloring any graph?
cstheory.stackexchange.com

9
The “sensitivity” of 2-colorings of the d-dimensional integer lattice
mathoverflow.net

8
Evidence that PPAD is hard?
cstheory.stackexchange.com

8
Fast convolution over small finite fields
cstheory.stackexchange.com

8
Computing any information about Max-3SAT
cstheory.stackexchange.com

7
Algorithm to Determine if (Union of Cartesian Products of Subsets) equals (Cartesian Product of Full Sets)
cstheory.stackexchange.com

7
How hard is it to count the number of local optima for a problem in PLS?
cstheory.stackexchange.com

6
Which results in complexity theory make essential use of uniformity?
cstheory.stackexchange.com

6
Two Variants of NP
cstheory.stackexchange.com

5
Subset $k$-product
cstheory.stackexchange.com