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