6.S078: Fine-Grained Algorithms and Complexity -- Fall 2020

Instructors: Virginia Vassilevska Williams and Ryan Williams

Teaching Assistant: Nicole Wein

Time: Monday/Wednesday 2:30pm--4pm, over Zoom (link will be sent to all registered students)`

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.

6.s078 now counts as an Independent Inquiry Subject for Course 6!

Due to the pandemic, we will experiment with a new, flipped format for the class. Instead of traditional lectures, we will provide lecture notes and other resources (such as papers and occasional videos), which students should digest before class. During normal class time (in Zoom sessions), we will discuss the relevant material and answer any questions, hopefully having fun discussions along the way! We can record the Zoom sessions for students who cannot attend, due to time zone and other issues. (Students should notify the course staff when such a situation arises.) Our teaching assistant Nicole will hold additional office hours.

• Three problem sets, about two weeks apart. 50% of grade.
• Class project (individual or with a partner). 50% of grade. It has the following components:
  • Project Proposal (1 page), due 10/29
  • Progress Report (2 pages), due 11/16
  • In-class presentation over Zoom - during the last 1-2 weeks of class
  • Final report (at least 3 pages), due 12/9

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.045 or 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.

• 11/16: Notes for lecture 20 are here
• 11/6: Notes for lecture 19 are here
• 10/30: Notes for lecture 18 are here
• 10/30: Notes for lecture 17 are here
• 10/16: Notes for lecture 16 are here
• 10/16: Notes for lecture 15 are here
• 10/16: Notes for lecture 14 are here
• 10/16: Notes for lecture 13 are here
• 10/15 Instructions for the Projects: Your project proposal is due 10/29 (two weeks from now). 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 10/29 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 10/29, 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/16) 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/9) should be at least three pages and should give a brief description of what you studied/proved/presented. Please let us know if you have any questions!
• 10/9 Notes for lecture 12 are here
• 10/9 Notes for lecture 11 are here
• 10/2 Notes for lecture 10 are here
• 10/2 Notes for lecture 9 are here
• 9/25 Notes for lecture 8 are here
• 9/25 Notes for lecture 7 are here
• 9/18 Notes for lecture 6 are here
• 9/18 Slides for lecture 5 are here
• 9/11 Notes for lectures 3 and 4 are here
• 9/5 Lecture 2 notes are here
• 9/3 Lecture 1 slides are here
• 8/28 Look here for fun stuff to happen!

• 9/2 Overview; SAT to OV, OV to Diameter
• 9/7 NO CLASS (Labor Day)
• 9/9 SETH, Sparsification, ETH, k-SUM
• 9/14 SAT Algorithms
• 9/16 SAT Algorithms continued
• 9/21 SETH-based lower bounds for Longest Common Subsequence; HW1 released
• 9/23 Algorithms for OV, APSP and SAT, Polynomial Method for Algorithms Design
• 9/28 Continue polynomial method algorithms
• 9/30 Problems equivalent to APSP
• 10/5 Algorithms for k-SUM; HW1 due
• 10/7 Equivalences between different versions of 3-SUM
• 10/13 (Tuesday class due to Columbus Day) Hardness based on 3-SUM; HW 2 out
• 10/14 Linear Decision Trees, Computing APSP; Paper list and project instructions out
• 10/19 Linear Decision Trees for k-SUM
• 10/21 Hardness for Dynamic Problems
• 10/26 Introduction to FPT; HW 2 due;
• 10/28 k-Vertex cover FPT algorithms and kernels
• 10/29 Project proposal due
• 11/2 Finding Long Paths;
• 11/4 Finding Long Paths Cont. HW3 out
• 11/9 Finding Long Paths and FPT Lower Bounds
• 11/11 NO CLASS (Veteran's day)
• 11/16 Fine-grained improvements prove circuit lower bounds; Project progress report due
• 11/18 New developments; HW 3 due
• 11/21-11/29 THANKSGIVING break
• 11/30 Project consultation / Q and A
• 12/2 Presentations 1
• 12/7 Presentations 2
• 12/9 Prensentations 3; Project report due