Simons Institute | Maximum Matching in $O(\log \log n)$ Passes in Dynamic Streams @SimonsInstituteTOC | Uploaded 1 week ago | Updated 4 hours ago
Janani Sundaresan (University of Waterloo)
https://simons.berkeley.edu/talks/janani-sundaresan-university-waterloo-2024-07-29
Sublinear Graph Simplification
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, Soheil Behnezhad, Christian Konrad and Kheeran K. Naidu.
Janani Sundaresan (University of Waterloo)
https://simons.berkeley.edu/talks/janani-sundaresan-university-waterloo-2024-07-29
Sublinear Graph Simplification
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, Soheil Behnezhad, Christian Konrad and Kheeran K. Naidu.
