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!

How we will run this subject:

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.

NOTE: The first lecture (Wednesday 9/2) will be an introductory synchronous lecture over Zoom. We will send the Zoom link to all registered students in the class by email, on Wednesday morning.

We want this class to be a relief from the "normal world", not a burden. We think that this self-study approach will help with that. Fine-grained complexity is a relatively new area with easy-to-understand gems, and there is likely much more to be found -- probably by you!


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.

Announcements (also see Piazza): Upcoming topics (the rough plan: subject to change!)