From Gaussian Measure to Partial Colorings and Linear Size Sparsifiers

on YouTube ↗55m

" summary

Proves a simple two-line polynomial algorithm: project a Gaussian onto K∩[-ε,ε]^n (convex program) and show with Gaussian concentration and a width inequality that a constant fraction of coordinates hit ±ε, yielding a fractional partial coloring in polynomial time when γ_n(K) ≥ e^{-αn}. Extends to produce spectral sparsifiers with O(n/ε^2) edges and weighted Laplacian (match known n/ε^2 guarantee). Analysis uses a trace-inverse potential and a Brownian-motion style update to control eigenvalues.

AI-written summary · about

" chapters (15)

1. 0:00Intro
2. 1:55Discrepancy theory
3. 4:22Spencer/Gluskin/Giannopolous Thm Theorem (1980)
4. 6:27Algorithmic Discrepancy
5. 8:24The Algorithm
6. 10:59Some facts and notation for Gaussians
7. 14:04Analysis
8. 21:24Gaussian close to large bodies Lemma
9. 26:28Graph Sparsification Theorem (Batson-Spielman-Srivastava '08)
10. 30:19A new sparsification algorithm
11. 33:50How to find partial colorings What do we know about the set
12. 40:02A coupling argument
13. 49:05One-dimensional intuition
14. 51:44One update step Use potential function
15. 52:30Open problems