An Unconditional Space-Approximation Lower Bound for Semi-Streaming Matching
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-\varepsilon)$-approximation to maximum matching requires $\Omega(\log(1/\varepsilon))$ passes for...