New Advances on Multi-Pass Graph Streaming Lower Bounds

on YouTube ↗01h 05m

" summary

Proves that semi‑streaming MIS needs Theta(log log n) passes by reducing bounded‑round communication to streaming, using round‑elimination on a matrix of instances and amplifying one‑pass hardness via copies, and embedding hard subinstances into a sparse skeleton built from Ruzsa–Szemerédi (RS) graphs (induced matchings). Gives an n^{4/3}-style two‑pass barrier from parameters and explains the recursive parameter blowup; open gaps remain for directed reachability and (1+ε)-matching.

AI-written summary · about

" chapters (9)

1. 0:00Introduction
2. 1:49Why study streaming lower bounds
3. 7:12Proving lower bounds via communication complexity
4. 19:51Round elimination for multi-pass bounds
5. 28:40Extending one-pass to two passes
6. 42:48Advanced round elimination and embeddings
7. 56:24RS graphs in hard instances
8. 1:00:09Open problems and state of the art
9. 1:03:29Q&A

" related talks

• 35mSuperlinear Lower Bounds for Multipass Graph ProcessingKrzysztof Onak · Information Theory in Complexity Theory and Combinatorics 2015
• 30mOptimal Lower Bounds for Distributed and Streaming Spanning Forest ComputationHuacheng Yu · Interactive Complexity 2018
• 26mA Framework for Adversarial Streaming via Differential Privacy and Difference EstimatorsIdan Attias, Edith Cohen, Moshe Shechner, Uri Stemmer · ITCS 2023
• 23mTowards General and Tight Hardness Results for Graph ProblemsChristian Komusiewicz · Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
• 52mFine-Grained Complexity and Algorithm Design for Graph Reachability and Distance ProblemsKarl Bringmann · Fine-Grained Complexity, Logic, and Query Evaluation 2023
• 31mSome Novel Computational Models to Think AboutD Sivakumar · Information Theory in Complexity Theory and Combinatorics 2015
• 46mDistributed Graph Techniques in the MPC ModelQuanquan C. Liu · Fine-Grained Complexity, Logic, and Query Evaluation 2023
• 28mCommunication Avoiding Algorithms for Linear Algebra and BeyondJim Demmel · Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013)