# 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*)