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

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.