An SDP-based Algorithmic Cheeger Inequality for Vertex Expansion

on YouTube ↗55m

" summary

An SDP relaxation for symmetric vertex expansion is formulated and shown to round to a cut by solving for vertex vectors, picking a random Gaussian projection, and sweeping thresholds, yielding an O(sqrt(log D)) approximation where D is the max neighborhood size. The same SDP extends to hypergraphs (approx factor sqrt(log R) where R is edge size) and ties to a diffusion parameter gamma_2; improving beyond sqrt(log D) is hard under Small Set Expansion.

AI-written summary · about

" chapters (18)

1. 0:00Intro
2. 1:29Graph eigenvalues
3. 5:07Talk outline
4. 9:42Cheeger inequality for vertex expansion Relaxing the 0,1 constraint
5. 11:09A semidefinite relaxation
6. 19:38Hypergraph Cheeger
7. 21:05Hypergraph dispersion
8. 23:42Dispersion and Eigenvalues Viewing this dispersion process as a (Markov) operator, the process is
9. 27:40Better algorithmic bounds?
10. 29:06Small Set Expansion Raghavendra-Steurer
11. 33:21A series of reductions LRV'13
12. 34:51Balanced Analytic expansion Vertices V and distribution Pover d+1 subsets, with marginal P, on vertices. For F:V - (0.1)
13. 41:38Gadgets for dictators
14. 43:25Analytic Expansion of Product Graphs
15. 44:13Soundness of the gadget Need to show that every subset far from a dictator has high analytic expansion
16. 44:30Invariance Principles
17. 46:54Analytic Expansion of the Gaussian Graph
18. 50:21Open questions