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.