Optimal Lower Bounds for Distributed and Streaming Spanning Forest Computation
summary
Fully dynamic streaming and simultaneous-distributed spanning forest problems get tight space and communication lower bounds: randomized linear AGM sketch gives an upper bound of roughly n log^3 n bits (more generally n · log(n/Δ) · log^2 n for error Δ), and the paper proves matching lower bounds for almost that Δ range, with an Ω(log^3 n) average message lower bound per player in the simultaneous model. Proof uses a reduction from universal relation, a three-part hard graph embedding, and shows the bounds are essentially tight; tiny-Δ regimes remain open.
AI-written summary · about
chapters (14)
- 0:00Start
- 4:33Fully dynamic spanning forest
- 8:57AGM sketch for simultaneous communication
- 10:00Main result 11
- 14:09Streaming algorithm
- 14:35Communication protocol
- 16:20Recall...
- 17:29Universal Relation UR
- 18:53Connection to UR
- 21:08Hand instances
- 24:26Hard distribution
- 25:05Reduction from UR
- 26:37Analyzing the protocol
- 27:47Open question
related talks
01h 05mNew Advances on Multi-Pass Graph Streaming Lower Bounds
30mLocal Problems on Trees from the Perspectives of Distributed Algorithms, Finitary Factors, and Descr
24mAsymptotically Tight Bounds on the Time Complexity of Broadcast and its Variants in Dynamic Networks
35mSuperlinear Lower Bounds for Multipass Graph Processing
31mNear-Optimal Distributed Implementations of Dynamic Algorithms for Symmetry Breaking Problems
46mTiming Matters: Online Dynamics in Broadcast Games
26mA Framework for Adversarial Streaming via Differential Privacy and Difference Estimators
01h 20mAn Introduction to Distributed, Massively Parallel, and Local Computation Algorithms