Graph Streaming Lower Bounds for Parameter Estimation and Property Testing via a Streaming XOR Lemma

Abstract

We study space-pass tradeoffs in graph streaming algorithms for parameter estimation and property testing problems such as estimating the size of maximum matchings and maximum cuts, weight of minimum spanning trees, or testing if a graph is connected or cycle-free versus being far from these properties. We develop a new lower bound technique that proves that for many problems of interest, including all the above, obtaining a $(1+\epsilon )$-approximation requires either $n^{\Omega (1)}$ space or $\Omega (1/\epsilon )$ passes, even on highly restricted families of graphs such as bounded-degree planar graphs. For multiple of these problems, this bound matches those of existing algorithms and is thus (asymptotically) optimal. Our results considerably strengthen prior lower bounds even for arbitrary graphs: starting from the influential work of [Verbin, Yu; SODA 2011], there has been a plethora of lower bounds for single-pass algorithms for these problems; however, the only multi-pass lower bounds proven very recently in [Assadi, Kol, Saxena, Yu; FOCS 2020] rules out sublinear-space algorithms with exponentially smaller $o(\log (1/\epsilon ))$ passes for these problems. One key ingredient of our proofs is a simple streaming XOR Lemma, a generic hardness amplification result, that we prove: informally speaking, if a $p$-pass $s$-space streaming algorithm can only solve a decision problem with advantage $\delta >0$ over random guessing, then it cannot solve XOR of $\ell$ independent copies of the problem with advantage better than ${\delta }^{\Omega (\ell )}$. This result can be of independent interest and useful for other streaming lower bounds as well.

In STOC 2021. 59 pages, 7 Figures. Version 2 fixes an error in the previous proof of the streaming XOR lemma

References in corpus (6)

• On Estimating Maximum Matching Size in Graph Streams
• A direct sum theorem in communication complexity via message compression
• Sublinear Estimation of Weighted Matchings in Dynamic Data Streams
• Testable Bounded Degree Graph Properties Are Random Order Streamable
• On Approximating Functions of the Singular Values in a Stream
• Multi-Pass Graph Streaming Lower Bounds for Cycle Counting, MAX-CUT, Matching Size, and Other Problems

Cited by in corpus (2)

• A Two-Pass Lower Bound for Semi-Streaming Maximum Matching
• Noisy Boolean Hidden Matching with Applications