Superlinear Lower Bounds for Multipass Graph Processing
summary
Shows that for P passes several basic graph tasks — testing whether two fixed vertices are within distance 2P+1, deciding perfect matching, and s–t reachability — require space n^{1+Ω(1/P)} rather than ~n polylog n; one-pass and previous N^2 bounds are recovered and the trivial n/P upper bound is separated. Proof embeds a P-player pointer chasing + information complexity lower bound into a dense edge stream, amplifies via a direct-sum style disjunction-of-instances, and avoids false collisions by random relabeling; argument loses a constant (≈2) from birthday-paradox restrictions.
AI-written summary · about
chapters (12)
- 0:00Intro
- 0:25Streaming Algorithms for Graphs
- 1:30One Pass vs. Multiple Passes
- 2:23Graph Streaming
- 4:38Comparison to Previous Results
- 6:06Related Results: Shortest Path(s)
- 7:47Construction for Perfect Matching
- 10:07Construction for Shortest Path
- 14:29Important Problem: Pointer Chasing Definition
- 17:15FKMSZ Lower Bound for BFS Their Problem: Compute p levels of BFS tree from
- 19:09Proof Overview
- 22:48Step 1
related talks
01h 05mNew Advances on Multi-Pass Graph Streaming Lower Bounds
58mCircuit Complexity and Connections I
23mTowards General and Tight Hardness Results for Graph Problems
52mFine-Grained Complexity and Algorithm Design for Graph Reachability and Distance Problems
01h 05mGraph Algorithms in the MPC Model
07mVertex Connectivity in Poly-logarithmic Max-flows
30mOptimal Lower Bounds for Distributed and Streaming Spanning Forest Computation
59mHardness for Graph Problems - Reductions Based on APSP and SETH