- Instructor: Josh Alman
- Time: Tuesdays 4:10 – 6:00 PM
- Classroom: TBA
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.
This is an advanced topics class in theoretical computer science, but it is open to everyone. The most important prerequisite is mathematical maturity (comfort with understanding and writing mathematical proofs). Students should also be very comfortable with algorithmic concepts and NP-completeness (e.g., from CSOR 4231).
There is no textbook for this course, but we will write lecture notes over the course of the semester. The following survey and similar courses could also be helpful resources.
- Survey by Virginia Vassilevska Williams (link)
- Course by Virginia Vassilevska Williams and Ryan Williams (link)
- Course by Karl Bringmann (link)
- Course by Timothy Chan (link)
- Course by Amir Abboud (link)