  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. Verbin and Yu [SODA 2011] introduced this problem and showed that any
single-pass streaming algorithm solving it requires $n^{1-\Omega(\frac{1}{k})}$
space. This result and the technique behind it -- the Boolean Hidden
Hypermatching communication problem -- has since been used extensively for
proving streaming lower bounds for various problems.
  Despite its significance and broad range of applications, the lower bound
technique of Verbin and Yu comes with a key weakness that is inherited by all
subsequent results: the Boolean Hidden Hypermatching problem is hard only if
there is exactly one round of communication and can be solved with logarithmic
communication in two rounds. Therefore, all streaming lower bounds derived from
this problem only hold for single-pass algorithms.
  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-\frac{1}{k^{\Omega(1/p)}}}$ space. As a corollary of this
result, we can extend many of previous lower bounds to multi-pass algorithms.
For instance, we can now prove that any streaming algorithm that
$(1+\epsilon)$-approximates the value of MAX-CUT, maximum matching size, or
rank of an $n$-by-$n$ matrix, requires either $n^{\Omega(1)}$ space or
$\Omega(\log{(\frac{1}{\epsilon})})$ passes. For all these problems, prior work
left open the possibility of even an $O(\log{n})$ space algorithm in only two
passes.
