An Unconditional Space-Approximation Lower Bound for Semi-Streaming Matching
cs.DS
Submitted: 2026-10-27
Updated: 2026-10-27
License: http://creativecommons.org/licenses/by/4.0/
The gist: 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.
Abstract
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-epsilon) -approximation to maximum matching requires Ω((1/epsilon)) passes for constant epsilon in (0,1). Prior to our result, such tradeoffs were proven only conditioned on a certain combinatorial assumption about the density of Ruzsa-Szemerédi 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-epsilon) -approximation for any epsilon > 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édi graphs. The second extends the two-level Ruzsa-Szemerédi 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.
Related papers
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time
- Fast Odd-Permutation Sums in Characteristic Two and Shortest Even Directed Cycles