Learn · MIT OpenCourseWare

Photo of a model of the Green Building at MIT, illuminated with a version of a Tetris game.

Course6.89023 lectures31 h 4 min

Algorithmic Lower Bounds: Fun with Hardness Proofs

Prof. Erik Demaine · Massachusetts Institute of Technology

Start with lecture 1 At MIT OpenCourseWare

About

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).

Lectures

Lecture Videos

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

Syllabus and materials

At MIT OpenCourseWare, as the course publishes them.

Credits and licence

Institution
Massachusetts Institute of Technology
Department
Electrical Engineering and Computer Science
Teacher
Prof. Erik Demaine
Term
Fall 2014
Level
Graduate
Language
English
Subjects
Mathematics, Computer science, Engineering
Source
MIT OpenCourseWare
Licence
CC BY-NC-SA 4.0, as MIT OpenCourseWare states it. Non-commercial use only. MIT OpenCourseWare's terms
Attribution
Prof. Erik Demaine. Algorithmic Lower Bounds: Fun with Hardness Proofs. Fall 2014. Massachusetts Institute of Technology: MIT OpenCourseWare, https://ocw.mit.edu/. License: Creative Commons BY-NC-SA.
Who can watch
MIT OpenCourseWare gives no rating. Invisible Network shows it to Tweens profiles and older, judged from what the source says about it. How courses are placed