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]

Lecture 19 Video     [previous] [next]

[+] Gap Inapproximability. Gap problem, gap-producing and gap-preserving reductions, PCP theorem, max E3-X(N)OR-SAT, max E3SAT, Label Cover (Max-Rep and Min-Rep), directed Steiner forest, node-weighted Steiner tree, Unique Games Conjecture.

This lecture is about gap problems: distinguishing between good and bad solutions, with a big gap in between those two notions. This perspective is particularly nice because we can turn NP-hardness of a decision problem into NP-hardness of approximation. It also often leads to tighter bounds on approximability. For example, we'll see a reduction that gives an optimal 7/8-inapproximability for Max E3SAT.

A big tool here is the PCP (Probabilistically Checkable Proofs) theorem, which won a Gödel Prize in 2001. We'll see how gap problem hardness naturally leads to probabilistically checkable proofs and vice versa.

Then we'll see the core PCP lower bound theorems, a problem called label cover (MinRep and MaxRep).

Finally, we'll cover the Unique Games Conjecture, which (if true) leads to further improved inapproximability constants.

Download Video: 360p, 720p

Handwritten notes, page 1/7[previous page][next page][PDF]

Handwritten notes, page 1/7[previous page][next page][PDF]

Slides, page 1/15[previous page][next page][PDF]

http://erikdemaine.org/papers/Tetris_IJCGA/ (slide from Lecture 3)

Slides, page 1/15[previous page][next page][PDF]