Andrew Drucker

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 an emphasis on computational complexity---the study of the inherent limits of efficient computation.

One important part of this field 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."

Recently I've also been excited about instance compression and kernelization. These are preprocessing schemes for NP-hard problems that try to "shrink" instances which have some underlying simplicity. I've shown new limits to the kind of instance compression we can hope to achieve for a number of natural problems. This work has (I feel) involved an intriguing mix of computational and information-theoretic ideas.

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.