Opening CSP Approximability: Optimization and Certification
CSP Approximability: Optimization and Certification
- Length
- 33 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 5: CSP optimization and approximation algorithms
Contrasts approximating CSPs with certifying upper bounds, running Goemans-Williamson on two geometric graphs.
Approximation and certification for constraint satisfaction problems start from the fact that maximizing the number of satisfied constraints is NP-hard. O'Donnell defines -approximation algorithms, which find a solution of value at least whenever the optimum reaches . He then defines certification algorithms, which output guaranteed upper bounds, and shows that every polynomial-time approximation algorithm also certifies. The Goemans-Williamson semidefinite relaxation for Max-Cut serves as the canonical certifier, and two geometric graphs show where its bound and its rounding diverge. A survey of E3-Sat, Max-Cut and Max-Bijection covers Johnson's 7/8 algorithm, the PCP theorem, Hastad's tight hardness and Khot's Unique Games Conjecture. The session, part of CMU 15-750, assumes NP-completeness and semidefinite programming.
Approximation and certification for constraint satisfaction problems start from the fact that maximizing the number of satisfied constraints is NP-hard. O'Donnell defines -approximation algorithms, which find a solution of value at least whenever the optimum reaches . He then defines certification algorithms, which output guaranteed upper bounds, and shows that every polynomial-time approximation algorithm also certifies. The Goemans-Williamson semidefinite relaxation for Max-Cut serves as the canonical certifier, and two geometric graphs show where its bound and its rounding diverge. A survey of E3-Sat, Max-Cut and Max-Bijection covers Johnson's 7/8 algorithm, the PCP theorem, Hastad's tight hardness and Khot's Unique Games Conjecture. The session, part of CMU 15-750, assumes NP-completeness and semidefinite programming.
PCP Theorem
Johnson 1972
Hastad 1997

This lecture
Lecture 65 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.
Your comment is kept while you sign up.Sign in
Karloff and Zwick 1997
Trevisan, Sorkin, Sudan, and Williamson
Khot, Minzer, and Safra (2018)