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