arXiv · Oct 27, 2026
An Unconditional Space-Approximation Lower Bound for Semi-Streaming Matching
By Liu YP, Naidu K, Nguyen HA et al.
We prove the first unconditional lower bound tradeoff between the number of passes and the approximation factor of maximum matchings in the semi-streaming model. Specifically, we show that any algorithm that outputs an (1-ε)-approximation to maximum matching requires Ω(log(1/ε)) passes for constant ε ∈ (0,1). Prior to our result, such tradeoffs were proven only conditioned on a certain combinatorial assumption about the density of Ruzsa-Szemer'edi graphs. The state-of-the-art unconditional lower bound rules out any approximation factor better than (8/9) in two passes but leaves open the possibility of a (1-ε)-approximation for any ε > 0 even in three passes. We provide two different proofs of our result: the first proof uses the recent hierarchical-embedding framework of Assadi, Konrad, Naidu, and Sundaresan (STOC 2024) along with combinatorial constructions using Ruzsa-Szemer'edi graphs. The second extends the two-level Ruzsa-Szemer'edi hierarchy of Konrad and Naidu (SODA 2024) beyond two levels and proves the corresponding communication lower bound directly by induction, rather than through a reduction to Index.