State of the Art* [with a gross oversimplification]
5
Motivation of this work
6
Studied Problems
7
Our Results
8
Our Approach in a Nutshell
9
Ruzsa-Szemeredi (RS) Graphs
10
Single-Pass Lower Bound
11
The Abstract Problem
12
"Finding": €-Solving Set Intersectio..
13
Lower Bound of Abstract Problem
14
Summary of First Pass
15
Summary of Second Pass
16
Concluding Remarks
Description:
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.
Near-Quadratic Lower Bounds for Two-Pass Graph Streaming Algorithms