Catalog

Algorithmic Lower Bounds: Fun with Hardness Proofs

Electrical Engineering and Computer Science MIT CC BY-NC-SA 4.0 23 lectures

6.890 Algorithmic Lower Bounds: Fun with Hardness Proofs is a class taking a practical approach to proving problems can't be solved efficiently (in polynomial time and assuming standard complexity-theoretic assumptions like P ≠ NP). The class focuses on reductions and techniques for proving problems are computationally hard for a variety of complexity classes. Along the way, the class will 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).

Syllabus

  1. 1 Lecture 1: Overview
  2. 2 Lecture 2: 3-Partition I
  3. 3 Lecture 3: 3-Partition II
  4. 4 Lecture 4: SAT I
  5. 5 Lecture 5: SAT Reductions
  6. 6 Lecture 6: Circuit SAT
  7. 7 Lecture 7: Planar SAT
  8. 8 Lecture 8: Hamiltonicity
  9. 9 Lecture 9: Graph Problems
  10. 10 Lecture 10: Inapproximabililty Overview
  11. 11 Lecture 11: Inapproximability Examples
  12. 12 Lecture 12: Gaps and PCP
  13. 13 Lecture 13: W Hierarchy
  14. 14 Lecture 14: ETH and Planar FPT
  15. 15 Lecture 15: #P and ASP
  16. 16 Lecture 16: NP and PSPACE Video Games
  17. 17 Lecture 17: Nondeterministic Constraint Logic
  18. 18 Lecture 18: 0- and 2-Player Games
  19. 19 Lecture 19: Unbounded Games
  20. 20 Lecture 20: Undecidable and P-Complete
  21. 21 Lecture 21: 3SUM and APSP Hardness
  22. 22 Lecture 22: PPAD
  23. 23 Lecture 23: PPAD Reductions

Course materials