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 2021: Decision-Making Under Uncertainty: Algorithms and Lower Bounds (Topics in Theoretical Computer Science). Description: In this class we will examine central tasks in learning, estimation, and decision-making with rewards and penalties. We will review fundamentals of statistics and decision theory, with an additional concern for efficient algorithms. We will then study topics in computational learning theory, online algorithms, and games against nature (decision processes). Where possible we will aim to understand barriers arising either from information-theoretic uncertainty (e.g. sample-complexity lower bounds) or from computational hardness conjectures. This class aims to build a broad toolkit applicable to several areas in CS and machine learning. The format is participatory and flexible to student interests, and the challenges and opportunities of e-learning. Students can expect to present topics/papers and engage in group discussion and problem-solving. Prerequisites: coursework in probability, and familiarity with linear algebra.

Winter 2021: Theory of Algorithms, Secs. 2-3. In collaboration with Prof. Lorenzo Orecchia. Held remotely by Zoom and Canvas (student portal).

Fall 2019: Analytic Methods for Complexity and TCS (Topics in Theoretical Computer Science)

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.