An Asymptotically Optimal Algorithm for Maximum Matching in Dynamic Streams

on YouTube ↗21m

" summary

An algorithm gives an alpha-approximate maximum matching in dynamic graph streams using n^2/alpha^3 bits of space (optimal up to constants) and works for alpha < n^{1/2}. It runs match-or-sparsify and a solver for the resulting sparse hard instance in parallel, uses random grouping and 1/alpha subsampling to recover one cross-edge per group, and implements a new sparse neighborhood recovery sketches primitive to avoid L0-sampler polylog overheads while assembling an Omega(n/alpha)-sized matching.

AI-written summary · about

" chapters (19)

1. 0:00Intro
2. 0:16Matching Problem
3. 0:43Streaming Setting
4. 1:48Lower Bound
5. 2:08Approximation
6. 2:30Previous work
7. 4:48Our Result
8. 5:42Algorithm
9. 7:04Approach
10. 7:41Match Or Sparsify
11. 9:25Similarity to Hard Instances
12. 9:54Solving Hard Instances
13. 11:04Grouping
14. 14:48Issues
15. 16:58Challenges
16. 17:35Sparse Neighborhood Recovery
17. 19:31Solving General Hard Instance
18. 19:44Summary
19. 20:37Open Problems