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

## Prof. Erik Demaine TAs: Sarah Eisenstat, Jayson Lynch

[Home]
[Lectures]
[Problem Sets]
[Project]
[Open Problems]
[Piazza]
[Accessibility]

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