Parameterized and Promised Streaming

on YouTube ↗37m

" summary

Promised streaming assumes a bound K on the solution and gets space F(K)·polylog N instead of poly(N). Concrete results: a matching-based insertion algorithm is tight at K^2 bits (lower bound), and a dynamic algorithm uses k-sparse recovery plus k-sampler plus timestamps to maintain a kernel in K^2 polylog N space, even when K is only guaranteed at the end; hashing into K buckets yields K^2 pair sketches. Implementations handle billion-edge graphs in minutes.

AI-written summary · about

" chapters (8)

1. 0:00Streaming algorithms for big networks
2. 4:38Promised streaming model
3. 12:14Parameterized streaming and vertex cover
4. 18:53Dynamic graph streams challenges
5. 22:09Key data structures: k-sparse recovery and k-sampler
6. 25:44Simplified vertex cover algorithm
7. 33:07Real-world applications and future directions
8. 35:14Q&A