Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams

Abstract

In the dynamic streaming model, an $n$-vertex input graph is defined through a sequence of edge insertions and deletions in a stream. The algorithms are allowed to process this stream in multiple passes while using O(n \poly\log{(n)}) space. This model has been introduced in the seminal work of Ahn, Guha, and McGregor (AGM) in 2012 and has been studied extensively since.

In this talk, we focus on approximating maximum matching in the dynamic stream model. An $O(1)$-approximation algorithm in $O(\log n)$ passes was already introduced by [AGM12], but improving the number of passes has remained elusive. We give a randomized sketching based algorithm that achieves an $O(1)$-approximation in only $O(\log \log n)$-passes and $O(n \poly \log n)$ space, which exponentially improves the state-of-art. Using standard techniques, the approximation ratio of this algorithm can be improved to (1+eps)-approximation for any constant eps > 0 with asymptotically the same space and number of passes.

Furthermore, we prove the first multi-pass lower bound for this problem, showing that $\Omega(\log \log n)$ passes are also necessary for any algorithm which finds an $O(1)$-approximation to maximum matching in $O(n \poly \log n)$ space.

Our upper and lower bounds collectively settle the pass-complexity of this fundamental problem in the dynamic streaming model. The talk however will primarily focus on the algorithmic part of our results.

This is joint work with Sepehr Assadi, Christian Konrad, Kheeran K. Naidu, and Janani Sundaresan.

Speaker Bio

Soheil Behnezhad is an Assistant Professor of Computer Science at Northeastern University. Before joining Northeastern, he was a Motwani Postdoctoral Fellow at Stanford University. He received his PhD from the University of Maryland and his BSc from Sharif University. His research focuses on theoretical computer science, particularly the foundations of big data algorithms---including sublinear-time, parallel, streaming, and dynamic algorithms---as well as graph algorithms. He has received Best Paper Awards at SODA 2023 and STOC 2025, and his work is supported by an NSF CAREER Award and a Google Research Award.