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 bookmarks subscriptions
Top Questions
Top Answers
34
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

20
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
The cozy neighborhoods of “P” and of “NP-hard”
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

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

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

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

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

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

8
Evidence that PPAD is hard?
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
Two Variants of NP
cstheory.stackexchange.com

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

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