6.1420/6.S974: Fixed Parameter and Fine-Grained Algorithms and Complexity -- Fall 2024

Instructors: Virginia Vassilevska Williams and Ryan Williams

Time: Tuesday/Thursday 11am--12:30pm, Room 34-304

Office Hours: TBA

Piazza page: PIAZZA.

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.

• Three problem sets, about two weeks apart. 60% of grade.
• Class project (individual or with a partner). 40% of grade:
  • Project Proposal (less than 1 page, 5%), due November 1
  • Progress Report (less than 2 pages, 5%), due November 14
  • In-class presentation (10%) - during the last two weeks of class
  • Final Report (at least 5 and no more than 10 pages, 20%), due December 10
• (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.

• 9/24 Notes for Lecture 7: [pdf]
• 9/24 Notes for Lecture 6: [pdf]
• 9/19 Notes for Lecture 5: [pdf] and [ppt]
• 9/17 Notes for Lecture 4: [pdf]
• Open problems session Monday at 4pm in 32-370
• 9/16 Notes for Lecture 3: [pdf]
• 9/9 Notes for Lecture 2: [pdf]
• 2018 Survey on FGC: [pdf]
• 9/9 PDF slides for Lecture 1: [pdf]
• 9/5 Look here for fun stuff to happen!

• 9/5 Overview; SAT to OV, OV to Diameter
• 9/10 Basic algorithmic tools in FGC
• 9/12 SETH, Sparsification, ETH, k-SUM
• 9/17 SAT Algorithms
• 9/19 SETH-based lower bounds for Longest Common Subsequence; HW1 out
• 9/24 Problems equivalent to APSP
• 9/26 Hardness for Dynamic Problems
• 10/1 Algorithms for OV, APSP and SAT, Polynomial Method for Algorithms Design
• 10/3 Continue polynomial method algorithms HW1 due
• 10/8 Algorithms for k-SUM; HW 2 out
• 10/10 Equivalences between different versions of 3-SUM;
• 10/15 NO CLASS (Indigenous Peoples' Day)
• 10/17 Hardness based on 3-SUM; Paper list and project instructions out
• 10/22 Linear Decision Trees, Computing APSP;
• 10/24 Linear Decision Trees for k-SUM; HW 2 due
• 10/29 Introduction to FPT
• 10/31 k-Vertex cover FPT algorithms and kernels; HW3 out
• 11/1 Project proposal due
• 11/5 Finding Long Paths
• 11/7 More FPT algorithms
• 11/12 FPT Lower Bounds; HW 3 due
• 11/14 Fine-grained improvements prove circuit lower bounds; Project progress report due
• 11/19 TBA
• 11/21 New developments; Optional progress report for additional feedback can be submitted here
• 11/26 TBA
• 11/28 NO CLASS (THANKSGIVING break)
• 12/3 Presentations
• 12/5 Presentations
• 12/10 Presentations; Project report due