General Information
- Instructor: Josh Alman
- Time: Tuesdays 2:10 – 4:00 PM
- Classroom: TBA
- TA: TBA
- Office Hours:
- Josh: Thursdays 4 – 5 PM in CSB 504 or by email/appointment
- TA: TBA
- Scribe Notes will be posted below
- Link to previous offering: 2022
Description
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, and see why we believe they are (or aren't?) difficult. We will give fine-grained reductions from these problems to 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.
Prerequisites
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).
Tentative Schedule
|
January 20 |
Introduction to the course. SETH, OV, and fine-grained reductions. |
|
|
January 27 |
SAT Algorithms: Sparsification, PPSZ, and improvements. |
|
|
February 3 |
OV-Hardness of Sequence Problems: Longest Common Subsequence, Edit Distance, Fréchet Distance. |
|
|
February 10 |
APSP: Connections to (min,+)-product, negative triangles, other applications. |
|
|
February 17 |
The polynomial method: Fastest known algorithms for OV and APSP. |
|
|
February 24 |
k-SUM: algorithms, variants, applications to computational geometry. |
|
|
March 3 |
Hardness of dynamic problems: SETH-based lower bounds, online matrix-vector multiplication. |
|
|
March 10 |
Algorithms in other models: linear decision trees, nondeterministic algorithms, barriers for fine-grained reductions. |
|
|
March 17 |
No meeting (Spring Recess) |
|
|
March 24 |
Parameterized Complexity day 1: introduction, Vertex Coloring, kernelization. |
|
|
March 31 |
Parameterized Complexity day 2: W hierarchy, connections with (S)ETH. |
|
|
April 7 |
Epilogue |
|
|
April 14 |
Student Presentations day 1. |
|
|
April 21 |
Student Presentations day 2. |
|
Other Resources
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)