Near-Quadratic Lower Bounds for Two-Pass Graph Streaming Algorithms

Explore a 25-minute IEEE conference talk on near-quadratic lower bounds for two-pass graph streaming algorithms. Delve into the streaming model, graph problems, and state-of-the-art techniques presented by authors Sepehr Assadi from Rutgers University and Ran Raz from Princeton University. Examine the motivation behind their work, studied problems, and key results. Gain insights into their approach, including Ruzsa-Szemeredi graphs, single-pass lower bounds, and the abstract problem of €-solving set intersection. Analyze the lower bound of the abstract problem and summaries of both the first and second passes. Conclude with remarks on this significant contribution to graph streaming algorithm research.

Streaming Model
Graph Problems
Graph Streaming
State of the Art* [with a gross oversimplification]
Motivation of this work
Studied Problems
Our Results
Our Approach in a Nutshell
Ruzsa-Szemeredi (RS) Graphs
Single-Pass Lower Bound
The Abstract Problem
"Finding": €-Solving Set Intersectio..
Lower Bound of Abstract Problem
Summary of First Pass
Summary of Second Pass
Concluding Remarks