Opening The Sum-of-Squares (SOS) Proof System
The Sum-of-Squares (SOS) Proof System
- Length
- 22 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 3: The Sum-of-Squares proof system
The Sum-of-Squares proof system certifies upper bounds on constraint satisfaction problems and on polynomials under polynomial constraints. O'Donnell builds it from the Sherali-Adams hierarchy by admitting squared polynomials of degree up to as axioms. He proves that a multilinear polynomial is non-negative on - inputs exactly when it is the multilinearization of a squared function. then matches the Goemans-Williamson semidefinite program for Max-Cut, and degree-4 SOS certifies graph conductance within . Linear equations over finite fields mark the limit: Gaussian elimination solves them, yet high-degree SOS cannot certify their unsatisfiability. Part of CMU 15-750, A Theorist's Toolkit, the session assumes Boolean Fourier analysis, semidefinite programming and spectral graph theory.
Your comment is kept while you sign up.Sign in
Derives Sum-of-Squares from Sherali-Adams, then matches degree-two SOS to the Goemans-Williamson Max-Cut SDP.
The Sum-of-Squares proof system certifies upper bounds on constraint satisfaction problems and on polynomials under polynomial constraints. O'Donnell builds it from the Sherali-Adams hierarchy by admitting squared polynomials of degree up to as axioms. He proves that a multilinear polynomial is non-negative on - inputs exactly when it is the multilinearization of a squared function. then matches the Goemans-Williamson semidefinite program for Max-Cut, and degree-4 SOS certifies graph conductance within . Linear equations over finite fields mark the limit: Gaussian elimination solves them, yet high-degree SOS cannot certify their unsatisfiability. Part of CMU 15-750, A Theorist's Toolkit, the session assumes Boolean Fourier analysis, semidefinite programming and spectral graph theory.
Aurora-Rao-Vazirani '09
This lecture
Lecture 68 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.