Fall 2025: Algorithmic Approaches to Lower Bounds
(graduate course)

Course Description

How can we prove lower bounds? That is, how can we prove that there are no efficient algorithms solving certain hard problems? 

This course will focus on an approach that has been fruitful in the last decade, which is proving lower bounds by designing algorithms: To prove that problem X cannot be solved by any efficient algorithm, we design an efficient algorithm that solves problem Y. 

We will learn which problems we need to algorithmically solve in order to prove lower bounds, study the proofs of why designing algorithms for these problems implies lower bounds, and see some recent algorithms and resulting lower bounds from the last few years.