6.1420: Fine-Grained Algorithms and Complexity -- Fall 2022
- Instructors: Virginia Vassilevska Williams and Ryan Williams
- Time: Tuesday/Thursday 2:30pm--4pm, Room 5-134
- Office Hours: V: 11:30am-12:30pm Wed, R: 3-4pm Wed
- Piazza page: PIAZZA.
Description:
In traditional computer science theory, the typical problems considered "hard" are problems
such as Boolean Satisfiability that are NP-Hard and maybe even require exponential time to solve. This course considers
problems that have already been deemed "easy", i.e. those that are known to have polynomial time algorithms and thus for which NP-hardness says nothing. The best known algorithms for many easy problems have high runtimes and are rarely used in practice. Improving these running times has been a longstanding open problem, with little to no progress. It is thus completely plausible that these algorithms are optimal. However, developing unconditional lower bounds seems nearly impossible with current techniques. A new, conditional theory of hardness has recently been developed, based around several plausible conjectures. The theory develops interesting reductions between seemingly very different problems, showing that the reason why the known algorithms have been difficult to improve is likely the same, even though the known runtimes of the problems of interest might be very different. The course will deal with this "fine-grained complexity" theory. We will see many reductions, and also connections to classical circuit complexity theory. We will also develop intriguing algorithmic techniques that achieve surprising improvements for a variety of problems.
The course will be heavily research-oriented with lots of open problems, and it will introduce you to new ways of thinking about existing theory.
Workload for this course:
- Three problem sets, about two weeks apart. 50% of grade.
- Class project (individual or with a partner). 50% of grade:
- Project Proposal (less than 1 page), due November 5
- Progress Report (less than 2 pages), due November 17
- In-class presentation - during the last two weeks of class
- Final Report (at least 5 and no more than 10 pages), due December 13
- (Optional): Open Problems Sessions! TBA. Come and learn about open problems. You might get good ideas for your class project!
Prerequisites: This is an advanced course, meant for upper level undergraduate students and beginning graduate students, but it is open to anyone.
Good familiarity with algorithmic concepts and good mathematical maturity is necessary. We will try to recall the concepts needed along the way.
Prerequisite: 6.1400 (6.045) or 6.1220 (6.046) or an equivalent course.
There is no textbook for the course, but we will have lecture notes and will catalogue additional reading material as we go.
Announcements (also see Piazza):
- 10/20 Instructions for the Projects: Your project proposal is due 11/5. You have two options for the project:
- Learn a Paper (or Papers). Peruse the following (huge and lovingly annotated) paper list: [PAPER LIST].
Your first option for a project is to select a paper or two from the list, email Virginia and Ryan when you do,
and the paper will be assigned to you in a first-come first-serve fashion. Your job is then to read the paper (or papers)
by yourself, understand it and do a presentation on it during the last two weeks of class.
If you go this route, after you get an acknowledgment that you have been successfully assigned the paper(s), on 11/5 you should submit a short (less than 1 page)
summary of the main results of the paper(s), and which result(s) you are most interested in and why.
- Prove New Theorems. This one can be done with a partner.
With this option you can choose to explore any open research problem in fine-grained complexity.
The goal would be to make some progress on the problem and learn something new (with the option of changing the problem later, if needed!).
During classes, we have mentioned several such open problems, but you can choose your own.
If you choose this option, email us in advance about it, and we can send you papers to read to get you up to speed.
On 11/5, submit a short 1 page description of the open problem you would like to explore, and how you plan to study it and attempt to approach it.
During the last two weeks of class you will do a presentation on your findings.
Note: in both cases, it is totally OK to change your project focus between the project proposal and the final presentation!
That is what the project progress report (due 11/17) is for: to give us a status update on how it's going, and what has changed from your
original proposal, if anything.
Also, it would be totally OK if you chose the second option (prove new theorems) but later switch to the learn-a-paper option.
(This is why you should tell us in advance about what problem you'd like to try, so we can send you papers to read.)
The final project report (due 12/13) should be at least five pages (and at most 10) and should give a brief description of what you studied/proved/presented.
Please let us know if you have any questions!
- 10/20 Notes from lecture 11: [pdf]
- 10/13 Notes from lecture 10: [pdf]
- 10/13 Notes from lecture 9: [pdf]
- 10/13 Notes from lecture 8: [pdf]
- 10/13 Notes from lecture 7: [pdf]
- 9/27 Notes from lecture 6: [pdf]
- 9/27 Slides from lecture 5: [powerpoint]
- 9/22 Notes from lecture 4: Handwritten notes and pdf notes
- 9/20 Notes from lecture 3: Handwritten notes and pdf notes
- 9/13 Notes for lecture 2: [pdf]
- 9/9 Slides from lecture 1: [powerpoint]
- 9/6 Look here for fun stuff to happen!
Upcoming topics (the rough plan: subject to change!)
- 9/8 Overview; SAT to OV, OV to Diameter
- 9/13 SETH, Sparsification, ETH, k-SUM
- 9/15 SAT Algorithms
- 9/20 SAT Algorithms continued
- 9/22 SETH-based lower bounds for Longest Common Subsequence; HW1 out
- 9/27 Algorithms for OV, APSP and SAT, Polynomial Method for Algorithms Design
- 9/29 Continue polynomial method algorithms
- 10/4 Problems equivalent to APSP
- 10/6 Algorithms for k-SUM; HW1 due
- 10/11 NO CLASS (Indigenous Peoples' Day)
- 10/13 Equivalences between different versions of 3-SUM; HW 2 out
- 10/18 Hardness based on 3-SUM
- 10/20 Linear Decision Trees, Computing APSP; Paper list and project instructions out
- 10/25 Linear Decision Trees for k-SUM
- 10/27 Hardness for Dynamic Problems; HW 2 due
- 11/1 Introduction to FPT
- 11/3 k-Vertex cover FPT algorithms and kernels; HW3 out
- 11/5 Project proposal due
- 11/8 Finding Long Paths
- 11/10 More FPT algorithms
- 11/15 FPT Lower Bounds; HW 3 due
- 11/17 Fine-grained improvements prove circuit lower bounds; Project progress report due
- 11/22 TBA
- 11/24 NO CLASS (THANKSGIVING break)
- 11/29 New developments
- 12/1 Presentations
- 12/6 Presentations
- 12/8 Presentations
- 12/13 Presentations; Project report due