6.890
Algorithmic Lower Bounds: Fun with Hardness Proofs
Fall 2014
Topics
- Introduction
- 3-partition I
- 3-partition II, 2–partition
- SAT (Satisfiability)
- SAT Reductions
- Circuit SAT
- Planar SAT
- Hamiltonicity
- Graph Problems
- Inapproximability Introduction
- Inapproximability Examples
- Gap Inapproximability
- Parameterized Complexity I: W Hierarchy
- Parameterized Complexity II: ETH & Planar
- P and ASP
- NP & PSPACE Video Games
- Nondeterministic Constraint Logic
- 0- and 2–player Games
- More Games
- Undecidability & P-completeness
- 3SUM & APSP
- PPAD (guest lecture by Constantinos Daskalakis)
- PPAD Reductions (guest lecture by Constantinos Daskalakis)
Readings
- There is no textbook for this class, but there are two recommended books, one book chapter, and several useful websites.
- Garey, Michael R., and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-completeness . W. H. Freeman & Co Ltd, 1979. ISBN: 9780716710448.
- Demaine, Erik, and Robert A. Hearn. Games, Puzzles, & Computation . A. K. Peters / CRC Press, 2009. ISBN: 9781568813226.
Sources
- Course catalogue ↗Historical OpenCourseWare
- MIT OCW calendar ↗
- MIT OCW syllabus ↗
- Historical MIT OpenCourseWare offering. Named reading entries and schedule topics are automatically extracted from the linked source pages.