Multi-Pass Graph Streaming Lower Bounds for Cycle Counting, MAX-CUT, Matching Size, and Other Problems

摘要: Consider the following gap cycle counting problem in streaming model: The edges of a 2-regular $n$ -vertex graph $G$ are arriving one-by-one stream and we promised that is disjoint union either $k$ -cycles or $2k$ for some small ; goal to distinguish between these two cases using limited memory. Verbin Yu [SODA 2011] introduced this showed any single-pass algorithm solving it requires $n^{1-\Omega(1/k)}$ space. This result proof technique behind it—the Boolean Hidden Hypermatching communication problem—has since been used extensively proving lower bounds various problems, including approximating MAX-CUT, matching size, property testing, matrix rank Schatten norms, unique games CSPs, many others. Despite its significance broad range applications, bound comes with key weakness also inherited by all subsequent results: hard only if there exactly one round and, fact, can be solved logarithmic rounds. Therefore, derived from hold algorithms. Our paper remedy state-of-affairs. We prove first multi-pass problem: Any $p$ -pass vs -cycles—or even Hamiltonian cycle-requires $n^{1-1/k^{\Omega(1/p)}}$ makes progress on multiple open questions line research dating back work Yu. As corollary simple (or no) modification prior reductions, extend previous For instance, now ( $1+\varepsilon$ ) -approximates value maximum an -by- matrix, $n^{\Omega(1)}$ space $\Omega(\log({}^{1}\!/\!_{\varepsilon}))$ passes. left possibility $O(\log n)$