Expander Decomposition in Dynamic Streams

on YouTube ↗24m

" summary

This work shows a dynamic-stream algorithm that produces an expander decomposition reaching the optimal ε–φ tradeoff while using O(n/φ^2) memory but requiring exponential time; a separate polynomial-time algorithm uses worse ε–φ tradeoff yet can be sublinear in m. The construction relies on linear sketches, a refined power cut sparsifier analysis and a cut-matching style recursion. Corollaries include a dynamic-stream distance oracle with stretch O(log n/φ) and O(ε m + n) edges.

AI-written summary · about

" chapters (15)

1. 0:00Intro
2. 0:15Expanders
3. 3:02Constructing expander decomposition
4. 4:11Application: distance oracle
5. 5:39Dynamic stream
6. 6:45Previous work
7. 9:19Outline
8. 9:44Expander testing
9. 11:28Expander decomposition testing
10. 13:50Power cut sparsifier
11. 15:55Constructing sparsifiers
12. 17:48Trivial approach
13. 18:55Recursive approach
14. 20:21Cut matching lemma
15. 23:15Open problems