Opening Pseudoexpectations
Pseudoexpectations
- Length
- 14 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 4: Before the lecture
Pseudoexpectations provide a dual interpretation for Sherali-Adams and Sum-of-Squares proof systems by modeling probability distributions on the Boolean cube. The lecture constructs the dual linear program for the Sherali-Adams system, translating axioms into non-negativity constraints over monomial variables. Using the maximum independent set problem on a triangle graph, it demonstrates how convex combinations of valid solutions satisfy the dual constraints. Finally, it explores pseudo-solutions that yield upper bounds exceeding the true optimum, highlighting the ongoing challenge of rounding these fractional solutions back to integral ones.

Your comment is kept while you sign up.Sign in
Builds the Sherali-Adams dual LP and tests it on maximum independent set in a triangle graph.
Pseudoexpectations provide a dual interpretation for Sherali-Adams and Sum-of-Squares proof systems by modeling probability distributions on the Boolean cube. The lecture constructs the dual linear program for the Sherali-Adams system, translating axioms into non-negativity constraints over monomial variables. Using the maximum independent set problem on a triangle graph, it demonstrates how convex combinations of valid solutions satisfy the dual constraints. Finally, it explores pseudo-solutions that yield upper bounds exceeding the true optimum, highlighting the ongoing challenge of rounding these fractional solutions back to integral ones.
This lecture
Lecture 69 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.