O(log log n) Passes is Optimal for Semi-Streaming Maximal Independent Set

on YouTube ↗34m

" summary

Shows an unconditional lower bound that any semi‑streaming algorithm that finds a maximal independent set with constant success probability requires Ω(log log n) passes, matching the best known upper bound. Proof combines a round elimination style induction with information‑complexity and message‑compression arguments and a combinatorial construction of generalized Ruzsa–Szemerédi graphs (fractal‑like hierarchical embeddings) that pack many vertex‑disjoint target subgraphs and force the stated communication/space tradeoff.

AI-written summary · about

" chapters (10)

1. 0:00Semi-streaming MIS intro
2. 1:16Locality in sublinear models
3. 3:11Graph streaming and MIS
4. 5:22Exponential pass speedup for MIS
5. 7:32Omega(log log n) passes lower bound
6. 10:07Communication complexity reduction
7. 13:58Round elimination techniques
8. 20:31Graph construction for lower bounds
9. 26:42Fractal graphs and Ruzsa-Szemerédi
10. 31:00Open questions in sublinear models