6.S078: Fine-Grained Algorithms and Complexity -- Spring 2018

Instructors: Virginia Vassilevska Williams and Ryan Williams
Time: Monday/Wednesday 2:30pm--4pm, 36-156
Office Hours: TBA
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:

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.046 or 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: Upcoming topics (the rough plan: subject to change!)