Opening NP-Hardness of Approximation
NP-Hardness of Approximation
- Length
- 16 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 2: Hardness of label cover
Hardness of approximation for constraint satisfaction problems starts from Label-Cover, the canonical source problem for inapproximability reductions. In a short session of CMU 15-750: A Theorist's Toolkit, O'Donnell states Raz's theorem that approximating Label-Cover to a fraction is NP-hard over large domains. Later results, including Moshkovitz's improvements, then yield hardness limits for Max-Sat and Max-Independent-Set. The Unique Games Conjecture restricts constraints to bijections, and under it Raghavendra's theorem makes the Sum-of-Squares semidefinite hierarchy optimal for every CSP. That result extends the Max-Cut bound of Goemans and Williamson. The 2018 proof of the 2-to-2 version, sub-exponential algorithms and the absence of explicit hard instances close the session, which assumes NP-completeness and basic reductions.
Your comment is kept while you sign up.Sign in
O'Donnell contrasts Label-Cover's projection constraints with the bijections required by the Unique Games Conjecture.
Hardness of approximation for constraint satisfaction problems starts from Label-Cover, the canonical source problem for inapproximability reductions. In a short session of CMU 15-750: A Theorist's Toolkit, O'Donnell states Raz's theorem that approximating Label-Cover to a fraction is NP-hard over large domains. Later results, including Moshkovitz's improvements, then yield hardness limits for Max-Sat and Max-Independent-Set. The Unique Games Conjecture restricts constraints to bijections, and under it Raghavendra's theorem makes the Sum-of-Squares semidefinite hierarchy optimal for every CSP. That result extends the Max-Cut bound of Goemans and Williamson. The 2018 proof of the 2-to-2 version, sub-exponential algorithms and the absence of explicit hard instances close the session, which assumes NP-completeness and basic reductions.
Raz Theorem
Raghavendra '09
KMS'18
This lecture
Lecture 85 of 89 of A Theorist's Toolkit.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above. Other lectures and books are below.
Press a chosen node again to open it.