Rounding via Low Dimensional Embeddings

on YouTube ↗27m

" summary

Shows a concrete rounding scheme using project to R2/R3 and hyperplane-style cuts that deliberately avoid heavy segments, yielding improved max‑cut guarantees on ε,γ small‑set expanders: Goemans–Williamson normally gives about 1−3√δ from an SDP, but here the algorithm finds a cut of value 1−O(δ/ε) (constants depend on γ), recovers similar refinements for Cheeger and parallel repetition, uses elementary low‑dimensional geometry instead of heavy linear algebra.

AI-written summary · about

" chapters (10)

1. 0:00Start
2. 0:01Rounding via Low Dimensional Embeddings
3. 0:20Motivation: techniques
4. 2:04Goemans-Williamson Algorithm
5. 4:15Alternative view
6. 5:16Example: Grothendieck Constant
7. 8:10Back to GW rounding
8. 9:13GW rounding - 2D view
9. 12:57Small-set expanders The analysis is optimal for general graphs. • We can do better on small-set-expanders.
10. 25:43Summary and open problems