Opening The Sherali-Adams Proof System
The Sherali-Adams Proof System
- Length
- 37 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 5: Introduction to the proof system
The Sherali-Adams proof system is a degree- hierarchy of linear programming relaxations for constraint satisfaction and combinatorial optimization. O'Donnell builds it heuristically, arithmetizing Max-2SAT clauses into multilinear polynomial inequalities and adding non-negativity axioms for 0-1 variables. A Max-Cut instance on a triangle exposes the limits of degree-2 reasoning and motivates axioms that hold for all true inequalities on at most variables. He then covers soundness, incompleteness, the static form of derivations, and automatizability in time by linear programming. Applications include treewidth- instances refuted in and random-graph Max-Cut bounds set against semidefinite programming. Session 21b of CMU's graduate course A Theorist's Toolkit assumes linear programming duality and Boolean Fourier analysis.

Your comment is kept while you sign up.Sign in
Builds Sherali-Adams from Max-2SAT arithmetization, then shows a triangle's Max-Cut defeats the degree-2 system.
The Sherali-Adams proof system is a degree- hierarchy of linear programming relaxations for constraint satisfaction and combinatorial optimization. O'Donnell builds it heuristically, arithmetizing Max-2SAT clauses into multilinear polynomial inequalities and adding non-negativity axioms for 0-1 variables. A Max-Cut instance on a triangle exposes the limits of degree-2 reasoning and motivates axioms that hold for all true inequalities on at most variables. He then covers soundness, incompleteness, the static form of derivations, and automatizability in time by linear programming. Applications include treewidth- instances refuted in and random-graph Max-Cut bounds set against semidefinite programming. Session 21b of CMU's graduate course A Theorist's Toolkit assumes linear programming duality and Boolean Fourier analysis.
This lecture
Lecture 67 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.