(Noisy) Gap Cycle Counting Strikes Back: Random Order Streaming Lower Bounds for Connected Components and Beyond
Sepehr Assadi, Janani Sundaresan · 2023
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 ≥ 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.