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