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

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.