Janani Sundaresan, Rutgers University

Abstract

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].

See: https://theory.cs.rutgers.edu/theory_seminar