Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

YouTube

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

IEEE via YouTube

Overview

Save Big on Coursera Plus. 7,000+ courses at $160 off. Limited Time Only!
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.

Syllabus

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

Taught by

IEEE FOCS: Foundations of Computer Science

Reviews

Start your review of Near-Quadratic Lower Bounds for Two-Pass Graph Streaming Algorithms

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.