General Information
- Instructor: Josh Alman
- Time: Tuesdays 4:10 – 6:00 PM
- Classroom: 451 Computer Science Building (directions)
- TA: Yuval Efron
- Office Hours:
- Josh: Thursdays 4 – 5 PM in CSB 504 or by email/appointment
- Yuval: Tuesdays 3 – 4 PM in location TBA or by email/appointment
- Scribe Notes will be posted below
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
|
September 6 |
Introduction to the course. SETH, OV, and fine-grained reductions. |
|
|
September 13 |
SAT Algorithms: Sparsification, PPSZ, and improvements. |
|
|
September 20 |
OV-Hardness of Sequence Problems: Longest Common Subsequence, Edit Distance, Fréchet Distance. |
|
|
September 27 |
APSP: Connections to (min,+)-product, negative triangles, other applications. |
|
|
October 4 |
The polynomial method: Fastest known algorithms for OV and APSP. |
|
|
October 11 |
k-SUM: algorithms, variants, applications to computational geometry. |
|
|
October 18 |
Hardness of dynamic problems: SETH-based lower bounds, online matrix-vector multiplication. |
|
|
October 25 |
Algorithms in other models: linear decision trees, nondeterministic algorithms, barriers for fine-grained reductions. |
|
|
November 1 |
Parameterized Complexity day 1: introduction, Vertex Coloring, kernelization. |
|
|
November 8 |
No meeting (Election Day) |
|
|
November 15 |
Parameterized Complexity day 2: W hierarchy, connections with (S)ETH. |
|
|
November 22 |
Epilogue |
|
|
November 29 |
Student Presentations day 1. |
|
|
December 6 |
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)