6.890 Algorithmic Lower Bounds: Fun with Hardness Proofs (Fall 2014)

Prof. Erik Demaine TAs: Sarah Eisenstat, Jayson Lynch

[Home] [Lectures] [Problem Sets] [Project] [Open Problems] [Piazza] [Accessibility]

Overview

Need to figure out when to give up the search for efficient algorithms?
Want to know why Tetris and Mario are computationally intractable?
Love seeing the connections between problems and how they can be transformed into each other?
Like solving puzzles that can turn into publishable papers?

This class takes a practical approach to proving problems can't be solved efficiently (in polynomial time and assuming standard complexity-theoretic assumptions like P ≠ NP). We focus on reductions and techniques for proving problems are computationally hard for a variety of complexity classes. Along the way, we'll create many interesting gadgets, learn many hardness proof styles, explore the connection between games and computation, survey several important problems and complexity classes, and crush hopes and dreams (for fast optimal solutions).

The ability to show a problem is computationally hard is a valuable tool for any algorithms designer to have. Lower bounds can tell us when we need to turn to weaker goals or stronger models of computation, or to change the problem we're trying to solve. Trying to find lower bounds can help us see what makes a problem difficult or what patterns we might be able to exploit in an algorithm. The hardness perspective can help us understand what makes problems easy, or difficult to solve.

We will organize an optional problem-solving session, during which we can jointly try to solve open problems focusing on proving problems (we think) are computationally hard. In the past, similar problem sessions in 6.849 and 6.851 have led to important new results and published papers, as well as class projects.

See also the sister course to this one being taught by MohammadTaghi Hajiaghayi simultaneously at the University of Maryland.

Topics

This is an advanced class on algorithmic reduction. We will focus on techniques for proving problems are complete with respect to various complexity classes, not on the complexity theory itself. Here is a tentative list of topics:

NP-completeness
- 3SAT and all its variations
- 3-partition
- Hamiltonicity
- 2D/3D geometric problems
PSPACE, EXPTIME, EXPSPACE
Games, Puzzles, and Computation
- Tetris
- Nintendo games: Super Mario Bros., The Legend of Zelda, Metroid, Pokémon, ...
- Sliding blocks and Rush Hour
- Constraint Logic
- Sudoku and other Nikoli pencil-and-paper games
- Chess, Go, Othello, and other board games
Inapproximability
- PCP theorem and OPT-preserving reductions
- APX-hardness (e.g., Vertex Cover)
- Set-cover hardness
- Group Steiner tree
- k-dense subgraph
- Label cover and Unique Games Conjecture (UGC)
- Independent set
Fixed-parameter intractability
- Parameter-preserving reductions
- W hierarchy
- Clique-hardness
3SUM-hardness (n² and the Exponential Time Hypothesis)
Counting problems (#P)
Solution uniqueness (ASP)
Game theory (PPAD)
Existential theory of the reals
Undecidability

Readings and Resources

There is no textbook for this class, but there are two recommended books, one book chapter, and several useful websites.

Computers and Intractability A Guide to the Theory of NP-Completeness: book by Michael R. Garey and David S. Johnson
Johnson's followup NP-completeness Columns
Games, Puzzles, & Computation: book by Robert A. Hearn and Erik D. Demaine — available at MIT from CRCnetBASE
The Design of Approximation Algorithms by David Williamson and David Shmoys: chapter 16 is about inapproximability — ebook avalible from the MIT Library, draft available for free download
Limits to Parallel Computation: P-Completeness Theory by Raymond Greenlaw, H. James Hoover, and Walter L. Ruzzo — available for free download
Complexity Zoo
A compendium of NP optimization problems
Erik's 6.046 notes proving some basic NP-hardness (3-Dimensional Matching, Subset Sum, 4-Partition)

Specifics

Lecture Time:	Tuesdays and Thursdays at 3:30pm–5:00pm
Lecture Room:	MIT room 2-105
First Lecture:	Thursday, September 4, 2014
Problem Session Time:	5-7pm Thursdays
Problem Session Room:	32-044
Office Hours Time:	Tuesday 5-7pm
Office Hours Location:	MIT room 34-303
Professor:	Erik Demaine, 32-G680
TAs:	Sarah Eisenstat, 32-G635
	Jayson Lynch, 32-G585B
Staff Email:	6890-staff at csail.mit.edu
Units:	3-0-9
Prerequisites:	6.046 or equivalent background in discrete mathematics and algorithms Alternatively, permission from the instructor. No background in computational complexity is required (though it doesn't hurt); all needed notions will be defined in this class.
Credit:	H-level. This subjects qualifies as a Theoretical Computer Science concentration subject or be counted as an AUS.
Requirements:	Attending lectures Problem sets Scribe notes for 1-2 lectures Written project and project presentation

Grading

There are three requirements for the class:

Attending lectures (unless you have a valid excuse, which you need to tell the course staff).
Scribing one, maybe two, lectures. Scribe notes must be typeset using LaTeX, and are due 4 days after lecture: Tuesday lectures are due Saturday at 11:59pm; Thursday lectures are due Monday at 11:59pm. A LaTeX template can be found here. We will then send comments and possibly expect revisions. We will send a sign-up email during the second week. Listeners may also be required to scribe one lecture. See 6.851 for examples of scribe notes.
Periodic problem sets. See the psets page for details. Problems will be posted there every two to three weeks, and will not be distributed otherwise.
Research-oriented final project (paper and presentation). We allow theoretical, experimental, survey, Wikipedia, and art final projects. See the project page for more details.

Participating

This is a brand new class. Help shape it with your feedback and content requests!

We welcome both undergraduate and graduate students from all universities, although officially this is a graduate class.

If you are interested in attending the class, for credit or as a listener, please join the 6890-students mailing list.

Past and Future

The class is offered only occasionally. The latest edition is Fall 2023. It was also offered in Spring 2019 as 6.892.