# An Unconditional Lower Bound for Two-Pass Streaming Algorithms for Maximum Matching Approximation

#### Abstract

In this paper, we give the first unconditional space lower bound for two-pass streaming algorithms for *Maximum Bipartite Matching* approximation. We show that every randomized two-pass streaming algorithm that computes a $(\frac{8}{9}+\delta)$-approximation to *Maximum Bipartite Matching*, for any constant $\delta > 0$, requires space $n^{1 + \Omega(\frac{1}{(\log \log n)^2})}$, where $n$ is the number of vertices of the input graph.

Previously, only a conditional lower bound by Assadi [SODA’22] was known that relates the quality of their lower bound to the maximum density of Ruzsa-Szemerédi graphs (RS-graphs) with matchings of linear sizes. In the best case, i.e., if very dense RS-graphs with linear-sized matchings exist, their lower bound rules out approximation ratios above $0.98$, however, with current knowledge, only approximation factors of $1-o(1)$ are ruled out.

Our lower bound makes use of the information cost trade-off of the *Index* problem in the two-party communication setting established by Jain et al. [JACM’09]. To the best of our knowledge, our work is the first that exploits this trade-off result in the context of lower bounds for multi-pass graph streaming algorithms.

**Conference paper**| SIAM

**Conference talk**| Slides

2024 © Kheeran K. Naidu