Andrew Drucker   

Andy

My CV: pdf    Email: adrucker@mit.edu

 

**NEWS:**
1. I am currently seeking a faculty position. If you are interested in hiring me, please be in touch!
2. I am on the PC for FOCS 2014. Please submit your most exciting and well-written papers (by April 2).

I study theoretical computer science. I recently (Aug. 2012) submitted my PhD thesis in the EECS Dept. at MIT. I'm very lucky to have had Scott Aaronson as my advisor. I am now beginning a postdoc at IAS, in Princeton, NJ. I have broad research interests, with a focus on computational complexity---the study of the inherent limits of efficient computation.

A main goal of my current work is to better understand the limits of some powerful algorithmic paradigms for solving NP-hard problems. One such paradigm is kernelization. A kernelization reduction is an algorithm that tries to "shrink" problem instances, a preprocessing step which makes exhaustive search more feasible. A second algorithmic paradigm I've studied is intelligent random guessing, in which one tries to guess a solution to the given problem in a clever way where one's success probability is larger than the naïve approach (one may then run many trials to get a solution with high probability, or decide none exists). I've shown new limits to the kind of algorithms we can hope to develop by either of these approaches. This work has (I feel) involved an intriguing mix of computational, probabilistic, and information-theoretic ideas.

Another major strand in complexity theory is the study of non-standard proof systems, which incorporate features like interaction with provers, probabilistic verification, and the manipulation of quantum states. These brain-bending proofs are surprisingly powerful, and I've helped to further illuminate their power.

Another theme that fascinates me is joint computation---the common situation in which we have multiple computational tasks to perform simultaneously. When can we cleverly combine computations to make them more efficient and reliable? Much of my work aims at better understanding the possibility and also the limits of such "computational synergies."

Outside of complexity theory, I've worked on problems in prediction and polynomial approximation. I also have a personal interest in using algorithmic ideas to better understand the power of human memory.