An Unconditional Space-Approximation Lower Bound for Semi-Streaming Matching

arXiv:2610.36577 · cs.DS · Submitted 2026-10-27 · Read on arXiv

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