6.890 Algorithmic Lower Bounds: Fun with Hardness Proofs (Fall '14)

Prof. Erik Demaine     TAs: Sarah Eisenstat, Jayson Lynch

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)