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.

• 10/29 Notes for Lecture 15: [pdf]
• 10/24 Notes for Lecture 14: [pdf]
• 10/22 Notes for Lecture 13: [pdf]
• 10/22 Instructions for the Projects: Your project proposal is due 11/1. 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/1 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/1, 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/14) 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.)
  You have the option to submit a second project progress report by 11/21 for feedback. (This is not for credit.)
  The final project report (due 12/10) 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/17 Notes for Lecture 12: [pdf]
• 10/10 Notes for Lecture 11: [pdf]
• 10/8 Notes for Lecture 10: [pdf]
• 10/3 Notes for Lecture 9: [pdf]
• 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 Polynomial Method for Algorithms Design
• 10/3 Static data structures and FGC 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 Exact Triangle and Sparse Triangle Listing: Hardness
• 10/22 Linear Decision Trees, Computing APSP;Paper list and project instructions out
• 10/24 Linear Decision Trees for k-SUM; HW 2 due on 10/27
• 10/29 When Min-Plus product is faster
• 10/31 Introduction to FPT
• 11/1 Project proposal due
• 11/5 k-Vertex cover FPT algorithms and kernels; HW 3 out
• 11/7 Finding Long Paths;
• 11/12 More FPT algorithms
• 11/14 FPT Lower Bounds; Project progress report due
• 11/19 Fine-grained improvements prove circuit lower bounds; HW 3 due
• 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