Andrew Drucker papers
Classical TCS:
On the Power of the Congested Clique Model. With Fabian Kuhn and Rotem Oshman. PODC 2014. Extended abstract: pdf
Nondeterministic Direct Product Reductions and the Success Probability of SAT Solvers. FOCS 2013. Long version: pdf
New Limits to Classical and Quantum Instance Compression. FOCS 2012. Full version: pdf Slides: pdf Extended tutorial slides: Part 1 Part 2 Part 3
Limitations of Lower-Bound Methods for the Wire Complexity of Boolean Operators. CCC 2012. Recipient of the Ronald V. Book Prize for Best Student Paper. Full version: pdf Slides: pdf
The Communication Complexity of Task Aggregation. With Fabian Kuhn and Rotem Oshman. PODC 2012. Conference version: pdf
High-Confidence Predictions under Adversarial Uncertainty. ITCS 2012. Recipient of the Best Student Paper Award. In special issue of TOCT for ITCS'12 (Vol 5(3), 2013). Full version: pdf Slides: pdf
Efficient Probabilistically Checkable Debates. RANDOM 2011. pdf Slides: pdf
Improved Direct Product Theorems for Randomized Query Complexity. Computational Complexity 21(2), 2012 (special issue on CCC 2011). Co-recipient of the Ronald V. Book Prize for Best Student Paper at CCC'11. Full version: pdf Slides: pdf
A PCP Characterization of AM. ICALP 2011. Available on ECCC. link Slides: pdf
Block Sensitivity of Minterm-Transitive Functions. Theoretical Computer Science (Notes), Vol. 412, Issue 41, 2011. Full version: pdf
Multitask Efficiencies in the Decision Tree Model. CCC 2009. Full version on arxiv. link
Quantum TCS:
(cross-listed) New Limits to Classical and Quantum Instance Compression. FOCS 2012. Full version: pdf Slides: pdf Extended tutorial slides: Part 1 Part 2 Part 3
Advice Coins for Classical and Quantum Computation. With Scott Aaronson. ICALP 2011. Available on ECCC. link Slides: pdf Alternate slides: pdf
Short Multi-Prover Quantum Proofs for SAT without Entangled Measurements. With Jing Chen. arxiv, 2010. link
A Full Characterization of Quantum Advice. With Scott Aaronson. Accepted to SIAM Journal on Computing (to appear). Also appeared in STOC 2010, and presented at QIP 2010. Full version: pdf Slides: pdf Alternate slides: pdf
Uniform Approximation by (Quantum) Polynomials. With Ronald de Wolf. Quantum Information and Computation, Vol. 11, No. 3, 2011. Full version: pdf
(Survey Paper) Quantum Proofs for Classical Theorems. With Ronald de Wolf. Theory of Computing Library Graduate Surveys, 2011. link Slides: pdf
The Power of Unentanglement. With Scott Aaronson, Salman Beigi, Bill Fefferman, and Peter Shor. Theory of Computing, Volume 5, 2009. Also appeared in CCC 2008. link
Human Computation:
Multiplying 10-digit numbers with Flickr: The power of recognition memory. Informal article. pdf
Theses:
(Ph.D. Thesis) The Complexity of Joint Computation. MIT, 2012. pdf
(Master's Thesis) PCPs for Arthur-Merlin Games and Communication Protocols . MIT, 2010. pdf