Opening Proof Complexity for CSPs: Sherali-Adams and Sum-of-Squares Proof Systems
Proof Complexity for CSPs: Sherali-Adams and Sum-of-Squares Proof Systems
- Length
- 13 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 4: Before the lecture
Proof complexity for constraint satisfaction problems treats an upper bound on an optimum as a formal proof. In session 66 of CMU 15-750, O'Donnell relaxes a 0-1 integer linear program to a linear program whose value bounds the true maximum. LP duality then becomes a proof system with indeterminates, axioms and one inference rule: non-negative linear combinations of constraints. Max independent set is the running example, where a crude bound gives way to a weighted combination of edge axioms. Cutting planes adds the rounding down of non-integer bounds on integer variables, a first step toward stronger hierarchies, with LP duality assumed throughout.
Your comment is kept while you sign up.Sign in
Recasts LP duality as a proof system on max independent set, then adds rounding to reach cutting planes.
Proof complexity for constraint satisfaction problems treats an upper bound on an optimum as a formal proof. In session 66 of CMU 15-750, O'Donnell relaxes a 0-1 integer linear program to a linear program whose value bounds the true maximum. LP duality then becomes a proof system with indeterminates, axioms and one inference rule: non-negative linear combinations of constraints. Max independent set is the running example, where a crude bound gives way to a weighted combination of edge axioms. Cutting planes adds the rounding down of non-integer bounds on integer variables, a first step toward stronger hierarchies, with LP duality assumed throughout.
Semialgebraic Proofs and Efficient Algorithm Design
This lecture
Lecture 66 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.