Max Cut with Linear Programs: Sherali-Adams Strikes Back

on YouTube ↗52m

" 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)

1. 0:00Intro
2. 0:29optimizing with relaxations
3. 3:36comparing relaxations
4. 4:45max cut
5. 5:43semidefinite relaxation
6. 9:01linear programming relaxations?
7. 12:44secret motivation: understanding technology
8. 15:07certifying with linear programs?
9. 17:44surprise!
10. 24:40random CSPs (constraint satisfaction problems)
11. 30:40the LP relaxation
12. 35:36eigenvalues & random walks
13. 38:30random walk embeddings
14. 46:22concluding

" related talks

• 49mExtremal Cuts of Sparse Random GraphsAmir Dembo · Random Instances and Phase Transitions (Simons Institute, 2016)
• 35mLocal Statistics, Semidefinite Programming, and Community Detection IISidhanth Mohanty · Computational Phase Transitions (Simons Institute, 2020)
• 47mSuccinct Representations and Efficient Algorithms Based on Linear ProgrammingSudipto Guha · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 33mLearning the Best Agorithm for Max-Cut, Clustering, and Other​ ​Partitioning ProblemsVaishnavh Nagarajan · Learning, Algorithm Design and Beyond Worst-Case Analysis
• 29mSampling Algorithms for Combinatorial Pure ExplorationAnupam Gupta · Optimization, Statistics and Uncertainty
• 01h 06mLP/SDP Hierarchies and Sum of Squares Proofs 4Ankur Moitra, Pablo Parrilo · Bridging Continuous and Discrete Optimization Boot Camp 2017
• 01h 01mNearest Neighbor Methods IIIlya Razenshteyn · Foundations of Data Science Boot Camp 2018
• 47mLearning Probabilistic Models for Graph Partitioning in the Presence of NoiseAravindan Vijayaraghavan · Learning, Algorithm Design and Beyond Worst-Case Analysis