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:
- Class Participation: 5% of grade - Come to class!
- Three problem sets, about two weeks apart. 45% of grade.
- Class project (individual or with a partner). 50% of grade. It has three components:
- Project Proposal (less than 1 page), due April 11
- Progress Report (less than 2 pages), due April 23
- In-class presentation - during the last two weeks of class
- (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.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:
- 5/14 Last lecture is here: [pdf]
- 4/27 Homework 3 is here, due May 4: [pdf]
- 4/27 Lecture 19 is here: [txt]
- Final presentation schedule: [pdf]
- 4/25 Lectures 17 and 18 are here: [txt]
- 4/25 Lecture 16 is here: [txt]
- 4/25 Lecture 14 is here: [pdf]
- 4/25 Lecture 13 is here: [txt]
- 4/25 Lecture 12 is here: [txt]
- Instructions for the Projects: You have two options for the project:
- First Option. Look at the following paper list: [html]. Your first option for a project is to select a paper from the list, email Virginia when you do, and the paper will be assigned to you in a first-come first-serve fashion. Your job is then to read this paper 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, submit a short (less than 1 page) summary of the main results, and which result(s) you are most interested in and why.
- Second Option. This one can be done with a partner. Hopefully you have had some time during this semester to think about potential projects. With this option you can choose to explore a research problem in fine-grained complexity. The goal would be to make some progress on the problem and learn something. During the course we have mentioned several such open problems. If you choose this option, 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.
- Homework 2, due April 5 is here: [pdf]
- 3/21 Lecture 11 is here: [pdf]
- 3/21 Lecture 10 is here: [pdf]
- 3/21 Lecture 9 is here: [txt]
- 3/18 Lecture 8 is here: [pdf]
- Homework 1, due March 9 is here: [pdf]
- 2/27 Lecture 5 is here: [pdf]
- 2/25 Lectures 3 and 4 are here: [pdf]
- 2/16 Lecture 2 notes are here: [pdf]
- 2/7 Lecture 1 slides are here: [pdf]
- 2/7 Look here for fun stuff to happen!
Upcoming topics (the rough plan: subject to change!)
- 2/7: Overview. SETH to OV, OV to 2-3 Diameter.
- Week 2: SETH and ETH, OV to LCS
- Weeks 3 and 4: Algorithms for OV, APSP and SAT, Polynomial Method for Algorithms Design
- Week 5: APSP and equivalences
- Weeks 6-7: 3SUM reductions, algorithms. Making more believable hypotheses.
- Week 8: Vacation
- Week 9: Algorithmic techniques for finding long paths in graphs
- Week 10: Finding Cliques and Hardness Assumptions based on Clique
- Week 11: Nondeterministic SETH, Merlin-Arthur SETH etc.
- Week 12: Other Fine-Grained Results.
- Weeks 13,14: Presentations.