[+] Gap Inapproximability. Gap problem, gapproducing and gappreserving reductions, PCP theorem, max E3X(N)ORSAT, max E3SAT, Label Cover (MaxRep and MinRep), directed Steiner forest, nodeweighted 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 NPhardness of a decision problem into NPhardness of approximation. It also often leads to tighter bounds on approximability. For example, we'll see a reduction that gives an optimal 7/8inapproximability 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.  

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] 