The theory of NP-hardness is able to distinguish between "easy" problems that have polynomial-time algorithms, and "hard" problems that are NP-hard. However, it is often not reasonable to label any problem with a polynomial-time algorithm as "easy", and in practice, it can make a huge difference whether an algorithm runs in, say, linear time, quadratic time, or cubic time. Nonetheless, the theory of NP-hardness is "too coarse" to make distinctions like this.

Fine-Grained Complexity is a new area which aims to address this issue. The theory involves careful "fine-grained reductions" between problems which show that a polynomial speedup for one problem would give a polynomial speedup for another. Through a web of such reductions, Fine-Grained Complexity identifies a small number of algorithmic problems whose best-known algorithms are conjectured to be optimal, and shows that assuming these conjectures, a wide variety of algorithms in many seemingly-different areas must also be optimal.

In this class, we will explore this new area and a variety of applications. We will study problems like Orthogonal Vectors, 3-SUM, and All-Pairs Shortest Paths, which are at the center of these conjectures, see why we believe they are (or aren't?) difficult. We will give fine-grained reductions to these problems from problems in many areas, including dynamic and approximation algorithms problems. We will also study the related area of parameterized complexity, which shows how NP-hard problems can become tractable when certain parameters describing the input are guaranteed to be small.

Evaluation will be primarily based on a final project. I will provide a list of suggestions for the project, but students are encouraged to relate their project to their interests. There will also be occasional (at most 3) homework assignments, and students will be asked to scribe a lecture.