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.