MIT · Computer Science

6.890 Algorithmic Lower Bounds: Fun with Hardness Proofs

Erik Demaine · 2014 · 23 free video 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…

▶ Play on Open Lecture HallCourse page ↗

Lectures

  1. Lecture 1: overview
  2. Lecture 2: 3 partition i
  3. Lecture 3: 3 partition ii
  4. Lecture 4: sat i
  5. Lecture 5: sat reductions
  6. Lecture 6: circuit sat
  7. Lecture 7: planar sat
  8. Lecture 8: hamiltonicity
  9. Lecture 9: graph problems
  10. Lecture 10: inapproximabililty overview
  11. Lecture 11: inapproximability examples
  12. Lecture 12: gaps and pcp
  13. Lecture 13: w hierarchy
  14. Lecture 14: eth and planar fpt
  15. Lecture 15: p and asp
  16. Lecture 16: np and pspace video games
  17. Lecture 17: nondeterministic constraint logic
  18. Lecture 18: 0 and 2 player games
  19. Lecture 19: unbounded games
  20. Lecture 20: undecidable and p complete
  21. Lecture 21: 3sum and apsp hardness
  22. Lecture 22: ppad
  23. Lecture 23: ppad reductions

From MIT OpenCourseWare · CC BY-NC-SA 4.0. More from MIT.

Open Lecture Hall is free, with no ads and no sign-up. It is not run by or connected to any university; the lectures are the universities' own free recordings, played from where they host them. About & rights