Max Cut with Linear Programs: Sherali-Adams Strikes Back
summary
Claim: linear programs from Sherali‑Adams level D can certify max‑cut ≲ 1/2+ε on graphs whose random‑walk eigenvalues are ≤ 1/√δ by using random‑walk spider embeddings and a fixed PSD certificate. Construction: embed K legs of length T (T ≈ log N / log δ), choose K ≈ (1/ε)^T, form a PSD matrix M whose quadratic form equals the average edge pseudo‑correlation plus O(1/√K). Conclusion: exp(log N / log δ) rounds suffice (polynomial size when δ is N^c, giving ~0.99).
AI-written summary · about
chapters (14)
- 0:00Intro
- 0:29optimizing with relaxations
- 3:36comparing relaxations
- 4:45max cut
- 5:43semidefinite relaxation
- 9:01linear programming relaxations?
- 12:44secret motivation: understanding technology
- 15:07certifying with linear programs?
- 17:44surprise!
- 24:40random CSPs (constraint satisfaction problems)
- 30:40the LP relaxation
- 35:36eigenvalues & random walks
- 38:30random walk embeddings
- 46:22concluding
related talks
49mExtremal Cuts of Sparse Random Graphs
35mLocal Statistics, Semidefinite Programming, and Community Detection II
47mSuccinct Representations and Efficient Algorithms Based on Linear Programming
33mLearning the Best Agorithm for Max-Cut, Clustering, and Other Partitioning Problems
29mSampling Algorithms for Combinatorial Pure Exploration
01h 06mLP/SDP Hierarchies and Sum of Squares Proofs 4
01h 01mNearest Neighbor Methods II
47mLearning Probabilistic Models for Graph Partitioning in the Presence of Noise