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

YouTube

Maximum Matching in O(log log n) Passes in Dynamic Streams

Simons Institute via YouTube

Overview

Save Big on Coursera Plus. 7,000+ courses at $160 off. Limited Time Only!
Explore a groundbreaking lecture on approximating maximum matching in dynamic streams. Delve into a randomized sketching-based algorithm that achieves an O(1)-approximation in O(log log n) passes and O(n poly log n) space, exponentially improving the state-of-the-art. Learn about the first multi-pass lower bound for this problem, demonstrating that Ω(log log n) passes are necessary for any algorithm finding an O(1)-approximation in O(n poly log n) space. Discover how these upper and lower bounds collectively settle the pass complexity of this fundamental problem in the dynamic streaming model. Focus primarily on the algorithmic aspects of the results, including techniques to improve the approximation ratio to (1+eps)-approximation for any constant eps > 0 with asymptotically the same space and number of passes.

Syllabus

Maximum Matching in $O(\log \log n)$ Passes in Dynamic Streams

Taught by

Simons Institute

Reviews

Start your review of Maximum Matching in O(log log n) Passes in Dynamic Streams

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.