Seminar Details

We study the space requirement for an additive approximation of number of connected components in random order streams through 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 and an n-vertex graph with vertex-disjoint union of either k-cycles or 2k-cycles, plus O(n/k) disjoint paths of length k-1 in both cases. The edges of this graph are partitioned between Alice and Bob randomly whose goal is to decide which case the graph belongs to with minimal communication from Alice to Bob.  

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 one-way communication complexity of NGC is \Omega(n) bits.

As a corollary of this result, we can prove streaming lower bounds for random order streams for graph problems. In particular, we show that any streaming algorithm that for every \eps > 0 estimates the number of connected components
of a graph presented in a random order stream to within an $\eps \cdot n$ additive factor requires $2^{\Omega(1/\eps)}$ space, settling a conjecture of Peng and Sohler [SODA 2018].