LP/SDP Hierarchies and Sum of Squares Proofs 3

on YouTube ↗59m

" summary

Part three shows an SOS/SDP proof that a triangle-free graph has at most asymptotically half the possible edges (an SOS version of Mantel’s theorem), by writing subgraph densities as polynomials D_H, introducing two-label flags F0 and F1, and exhibiting a PSD quadratic form whose expectation equals half minus the edge density up to an explicit O(1/N) collision error. It translates Razborov’s flag algebra machinery into constant-size SOS/representation-theory reductions.

AI-written summary · about

" chapters (13)

1. 0:00Introduction to sum of squares
2. 1:36Extremal graph theory
3. 4:20Mantel's theorem
4. 6:49Polynomial representations
5. 10:41Working with graph ideals
6. 13:59Elementary identities
7. 18:31Introduction to flags
8. 22:29Flag density experiments
9. 30:23Pairwise flag identities
10. 35:56Proving Mantel's theorem
11. 42:36Flag algebra discussion
12. 47:34Future directions and quantum
13. 50:08Technical details and QA

" related talks

• 32mLocal Statistics, Semidefinite Programming, and Community DetectionJess Banks · Computational Phase Transitions (Simons Institute, 2020)
• 31mA Positivity-First Approach to Sum-of-Squares Over the HypercubeTim Kunisky · Computational Phase Transitions (Simons Institute, 2020)
• 47mPlanted Clique, Sum-of-Squares and Pseudo-CalibrationAnkur Moitra · Random Instances and Phase Transitions (Simons Institute, 2016)
• 01h 04mFrom Proofs to Algorithms for Machine Learning ProblemsDavid Steurer · Hierarchies, Extended Formulations and Matrix-Analytic Techniques (2017)
• 35mLocal Statistics, Semidefinite Programming, and Community Detection IISidhanth Mohanty · Computational Phase Transitions (Simons Institute, 2020)
• 44mCombinatorial Characterizations in Semidefinite Programming Duality: ...Gabor Pataki · Hyperbolic Polynomials and Hyperbolic Programming
• 27mWeak Decoupling, Polynomial Folds, and Approximate Optimization over the SphereVijay Bhattiprolu · Hierarchies, Extended Formulations and Matrix-Analytic Techniques (2017)
• 29mSum Of Squares Lower Bounds Versus Low-Degree Polynomial Lower BoundsAaron Potechin · Rigorous Evidence for Information-Computation Trade-offs