Extended Formulations 2

on YouTube ↗01h 00m

" summary

Shows a concrete lower bound for the correlation polytope by extracting a submatrix of its slack matrix with entries 1 for disjoint 0/1 vectors and 0 for pairs sharing one index, using a rectangle-cover induction to get extension complexity ≥ 1.5^n (and a related nonnegative-rank witness of about 2^n). Then develops SDP lifts: SDP extension size equals PSD-rank, gives a 3×3 lift of the square, an n+1 lift for perfect graphs, and a construction with SDP lift size O(log n) for regular n-gons, tying lifts to sum-of-squares certificates from low-dimensional subspaces.

AI-written summary · about

" chapters (14)

1. 0:00Intro
2. 0:28Correlation polytope (3)
3. 3:07Incomplete slack matrices
4. 4:36Correlation polytope (5)
5. 14:25Semidefinite programming extended formulations
6. 16:11Examples of SDP lift
7. 20:46Existential question
8. 28:19Slack matrix
9. 29:53Positive semidefinite rank
10. 30:57Example of positive semidefinite factorization
11. 32:32SDP lifts and PSD rank
12. 47:52Connection with sums of squares: example 1
13. 50:33Example 2. polygons
14. 57:00Hierarchies and extended formulations