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

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 -approximation to Maximum Bipartite Matching, for any constant ɛ > 0, requires space , 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-Szemeredi 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.