  We continue the study of the communication complexity of gap cycle counting
problems. These problems have been introduced by Verbin and Yu [SODA 2011] and
have found numerous applications in proving streaming lower bounds. In the
noisy gap cycle counting problem (NGC), there is a small integer $k \geq 1$ and
an $n$-vertex graph consisted of vertex-disjoint union of either $k$-cycles or
$2k$-cycles, plus $O(n/k)$ disjoint paths of length $k-1$ in both cases
(``noise''). The edges of this graph are partitioned between Alice and Bob
whose goal is to decide which case the graph belongs to with minimal
communication from Alice to Bob.
  We study the robust communication complexity -- `a la Chakrabarti, Cormode,
and McGregor [STOC 2008] -- of NGC, namely, when edges are partitioned randomly
between the players. This is in contrast to all prior work on gap cycle
counting problems in adversarial partitions. While NGC can be solved trivially
with zero communication when $k < \log{n}$, we prove that when $k$ is a
constant factor larger than $\log{n}$, the robust (one-way) communication
complexity of NGC is $\Omega(n)$ bits.
  As a corollary of this result, we can prove several new graph streaming lower
bounds for random order streams. In particular, we show that any streaming
algorithm that for every $\varepsilon > 0$ estimates the number of connected
components of a graph presented in a random order stream to within an
$\varepsilon \cdot n$ additive factor requires $2^{\Omega(1/\varepsilon)}$
space, settling a conjecture of Peng and Sohler [SODA 2018]. We further discuss
new implications of our lower bounds to other problems such as estimating size
of maximum matchings and independent sets on planar graphs, random walks, as
well as to stochastic streams.
