6.892 Algorithmic Lower Bounds: Fun with Hardness Proofs (Spring 2019)
Prof. Erik Demaine
TAs: Jeffrey Bosboom, Jayson Lynch
[Home] [Lectures]
[Problem Sets] [Project]
[Coauthor]
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 complexitytheoretic 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.
Inverted Lectures
This year, we're experimenting with inverted lectures:
most material is covered in video lectures
recorded in 2014 (already watched by over 14,000 people), which you can
conveniently play at faster speed than real time.
Inclass time will be focused on inclass problem solving,
with some new material presented by the professor and/or guest lecturers.
Particularly unusual is that the problems we'll solve in groups will include
a chooseyourownmix of
problemset style problems with known solutions,
coding problems for those who love programming,
and open research problems that no one knows the answer to,
with the goal of publishing papers about whatever we discover.
(The past offering of this class led to over a dozen published papers.)
You can work on whatever type of problem most interests you.
To facilitate collaboration, we'll be using a new
opensource software platform
called Coauthor,
along with Github for
(optional) coding.
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:
 NPcompleteness
 3SAT and all its variations
 3partition
 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 pencilandpaper games
 Chess, Go, Othello, and other board games
 Inapproximability
 PCP theorem and OPTpreserving reductions
 APXhardness (e.g., Vertex Cover)
 Setcover hardness
 Group Steiner tree
 kdense subgraph
 Label cover and Unique Games Conjecture (UGC)
 Independent set
 Fixedparameter intractability
 Parameterpreserving reductions
 W hierarchy
 Cliquehardness
 3SUMhardness (n^{2} 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 NPCompleteness: book
by Michael R. Garey and David S. Johnson
 Johnson's followup NPcompleteness 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: PCompleteness 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 NPhardness (3Dimensional Matching, Subset Sum, 4Partition)
Specifics
Class Time: 
Wednesdays at 7:00pm–9:30pm 
Class Room: 
MIT room
32082

First Class: 
Wednesday, February 6, 2019 
Bonus Time: 
Thursdays at 7:00pm–9:00pm (optional) 
Bonus Room: 
MIT room
32082 
Professor: 
Erik Demaine,
32G680 
TAs: 
Jeffrey Bosboom,
32G632 

Jayson Lynch,
32G580 
Staff Email: 
6892staff at csail.mit.edu 
Units: 
309 
Prerequisites: 
6.006
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: 
Graduate, Independent Inquiry or AAGS (Theoretical Computer Science concentration). 


Participating
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 do the following:
 Join the 6892students mailing list.
 Sign up for an account on Coauthor
 Fill out this signup form
Grading
There are five requirements for the class:
 Watching lecture videos.
Be sure to fill out the linked feedback forms.
 Attending inperson classes (except when you have a valid excuse,
which you need to tell the course staff).
In particular, you must participate weekly
by posting or being @mentioned in a post on Coauthor.
 Solving problem sets.
 Revise existing scribe notes for one lecture
(or maybe two), according to your own inspiration for improvement
and feedback from fellow students.
The entire calendar for the course has been posted,
so you can select a lecture that interests you.
We will circulate a signup sheet during the second week.
Scribe notes are generally due noon on Tuesday after the corresponding
class (but extensions are possible).
 Researchoriented final project
(paper and presentation).
We allow theoretical, experimental, survey, Wikipedia, and art final projects.
See the project page for more details.
Past and Future
The class is offered only occasionally. It was given in
Fall 2014
as 6.890.