The Sketching Complexity of Graph Cuts

on YouTube ↗01h 06m

" summary

Claim: any graph-format sparsifier that preserves all cuts needs n/ε^2 lower bound edges, but allowing a non-graph sketch of size O(n/ε polylog n) with a per-query high‑probability guarantee reduces the dependence to 1/ε. Construction: downsample edges by ≈1/(ε^2·v), perform a recursive sparse-cut decomposition, store cross‑cut edges exactly, store degrees and one/ε sampled outgoing edges per vertex; estimator uses degrees minus sampled internal edges to cut variance. Proof of the lower bound uses a communication‑complexity reduction (the Index‑Gap‑Hamming reduction). Application: composable sketches for global minimum cut.

AI-written summary · about

" chapters (20)

1. 0:00Intro
2. 0:35Graph compression
3. 2:40Problem definition
4. 4:00Cut sparsifiers: constructions
5. 5:04Dependence on a ?
6. 6:55Our results
7. 9:40Motivating example
8. 19:16ii Sketch size
9. 21:55iii Estimation
10. 24:05Estimation illustration
11. 29:21iii Correctness
12. 31:09Why not cross-cut edges?
13. 34:21Inside-edges estimate
14. 36:16Wrap-up of upper bound
15. 39:39An application
16. 41:00Sketching for global min-cut
17. 45:11Lower Bound
18. 46:55Proof outline
19. 53:20Index(Gap-Ham) via cut-sketch H
20. 58:20Intuition