(Noisy) Gap Cycle Counting Strikes Back: Random Order Streaming Lower Bounds for Connected Components and Beyond

Sepehr Assadi, Janani Sundaresan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

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. We study the robust communication complexity of NGC-à la Chakrabarti, Cormode, and McGregor [STOC 2008]-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 < logn, we prove that when k is a constant factor larger than logn, the robust (one-way) communication complexity of NGC is ω(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 > 0 estimates the number of connected components of a graph presented in a random order stream to within an · n additive factor requires 2ω(1/") 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.

Original languageEnglish (US)
Title of host publicationSTOC 2023 - Proceedings of the 55th Annual ACM Symposium on Theory of Computing
EditorsBarna Saha, Rocco A. Servedio
PublisherAssociation for Computing Machinery
Pages183-195
Number of pages13
ISBN (Electronic)9781450399135
DOIs
StatePublished - Jun 2 2023
Event55th Annual ACM Symposium on Theory of Computing, STOC 2023 - Orlando, United States
Duration: Jun 20 2023Jun 23 2023

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Conference

Conference55th Annual ACM Symposium on Theory of Computing, STOC 2023
Country/TerritoryUnited States
CityOrlando
Period6/20/236/23/23

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • communication complexity
  • connected components
  • graph streaming
  • random order streams

Fingerprint

Dive into the research topics of '(Noisy) Gap Cycle Counting Strikes Back: Random Order Streaming Lower Bounds for Connected Components and Beyond'. Together they form a unique fingerprint.

Cite this