6.5440 Algorithmic Lower Bounds: Fun with Hardness Proofs (Fall 2023)

Prof. Erik Demaine       TAs: Josh Brunner, Lily Chung, Jenny Diomidova

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)