Andrew Drucker   

Assistant Professor of Computer Science           University of Chicago


I study theoretical computer science. In 2015 I joined the CS Department of the University of Chicago.

My CV: pdf    Email:

Professional service: PC member for ITCS'13, FOCS'14, CCC'15, FOCS'16, STOC '17, ITCS'18.

Please READ THIS before contacting me with requests for postdocs, other jobs, or advice. Thank you.


Available here (with selected slides)


Spring 2019: Fine-Grained Algorithms and Complexity (Topics in Theoretical Computer Science)

Winter 2019: Theory of Algorithms (Sections 1 & 2)

Spring 2018: Constructive and Nonconstructive Methods in Combinatorics and TCS (Topics in Theoretical Computer Science)

Winter 2018: Honors Theory of Algorithms

Spring 2017: Theory of Algorithms

Winter 2017: Honors Theory of Algorithms

Fall 2016: Analysis and Approximation of Boolean Functions (Topics in Theoretical Computer Science)

Spring 2016: Honors Theory of Algorithms

Winter 2016: Theory of Algorithms

Fall 2015: Circuit Complexity (Topics in Theoretical Computer Science)

My research:

I have broad interests, with a focus on computational complexity---the study of the inherent limits of efficient computation. Specific interests include:

• achieving a better understanding of the limits of powerful algorithmic paradigms for solving NP-hard problems, such as kernelization (efficient preprocessing of the input) and intelligent random guessing to obtain solutions;

• the study of non-standard proof systems, which incorporate features like interaction with provers, probabilistic verification, and the manipulation of quantum states;

• prospects and limits to efficient joint computation, in cases where we have multiple computational tasks to perform simultaneously, and where we may hope cleverly combine computations to make them more efficient and reliable.

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.