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

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.

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