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