On Graph Spectra and Small Set Expansion

on YouTube ↗59m

" summary

Gives concrete algorithms and constructions: shows you can distinguish small‑set expansion up to a barrier of sqrt(ε log(1/δ)) and proves a higher‑order Cheeger: from λ_k one finds ~k/2 disjoint sets whose worst expansion is ≤ sqrt(λ_k log k). The rounding uses k random Gaussian projections plus “keep largest coordinate” rounding; analysis uses hypercontractivity and control of variance via orthogonal eigenvectors. Presents the short code graph: a derandomized noisy‑hypercube built from k‑wise independence and local‑testable codes that yields exponentially many small eigenvalues while preserving small‑set expansion.

AI-written summary · about

" chapters (13)

1. 0:00Introduction
2. 0:43Small set expansion problem
3. 3:23Algorithmic state of the art
4. 5:58Unique games conjecture
5. 7:27Spectral graph foundation
6. 12:29Higher order inequalities
7. 17:32Spectral algorithm design
8. 20:12Proof sketch
9. 26:01Analysis and random rotation
10. 37:15Construction of graphs
11. 41:56Noisy hypercube analysis
12. 45:22Subset subgraph construction
13. 52:14Open questions and discussion