6.890 Algorithmic Lower Bounds: Fun with Hardness Proofs (Fall '14)
Prof. Erik Demaine TAs: Sarah Eisenstat, Jayson Lynch
[Home]
[Lectures]
[Problem Sets]
[Project]
[Open Problems]
[Piazza]
[Accessibility]
Visual Overview of Video Lectures
Lecture 1: Introduction
Lecture 2: 3-partition I
Lecture 3: 3-partition II
Lecture 4: SAT
Lecture 5: SAT Reductions
Lecture 6: Circuit SAT
Lecture 7: Planar SAT
Lecture 8: Hamiltonicity
Lecture 9: Graph Problems
Lecture 10: Inapproximability Intro
Lecture 11: Inapproximability Examples
Lecture 12: Gap Inapproximability
Lecture 13: Parameterized Complexity I: W Hierarchy
Lecture 14: Parameterized Complexity II: ETH & Planar
Lecture 15: #P and ASP
Lecture 16: NP & PSPACE Video Games
Lecture 17: Nondeterministic Constraint Logic
Lecture 18: 0- and 2-player games
Lecture 19: More Games
Lecture 20: Undecidability & P-completeness.
Lecture 21: 3SUM & APSP
Lecture 22: PPAD (guest lecture by Constantinos Daskalakis)
Lecture 23: PPAD Reductions (guest lecture by Constantinos Daskalakis)