Learn · Algorithmic Lower Bounds: Fun with Hardness Proofs

Lecture 10 of 23Lecture Videos1 h 19 min

Lecture 10: Inapproximabililty Overview

Prof. Erik Demaine · Massachusetts Institute of Technology

At MIT OpenCourseWare Transcript

Credits and licence

From
Algorithmic Lower Bounds: Fun with Hardness Proofs, Massachusetts Institute of Technology (at MIT OpenCourseWare)
Licence
CC BY-NC-SA 4.0, as MIT OpenCourseWare states it. Non-commercial use only.
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
Tweens profiles and older. How courses are placed

All the lectures

  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