6.892 Algorithmic Lower Bounds: Fun with Hardness Proofs (Spring 2019)

Prof. Erik Demaine       TAs: Jeffrey Bosboom, Jayson Lynch

Visual Overview of Video Lectures

Lecture 1: OPTIONAL — 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: #P and ASP

Lecture 11: NP & PSPACE Video Games

Lecture 12: Nondeterministic Constraint Logic

Lecture 13: 0- and 2-player games

Lecture 14: More Games

Lecture 15: Undecidability & P-completeness.

Lecture 16: Inapproximability Intro

Lecture 17: Inapproximability Examples

Lecture 18: Gap Inapproximability

Lecture 19: Parameterized Complexity I: W Hierarchy

Lecture 20: Parameterized Complexity II: ETH & Planar

Lecture 21: OPTIONAL — 3SUM & APSP

Lecture 22: OPTIONAL — PPAD (guest lecture by Constantinos Daskalakis)

Lecture 23: OPTIONAL — PPAD Reductions (guest lecture by Constantinos Daskalakis)