Tight distributed sketching lower bound for connectivity

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

1 Scopus citations

Abstract

In this paper, we study the distributed sketching complexity of connectivity. In distributed graph sketching, an n-node graph G is distributed to n players such that each player sees the neighborhood of one vertex. The players then simultaneously send one message to the referee, who must compute some function of G with high probability. For connectivity, the referee must output whether G is connected. The goal is to minimize the message lengths. Such sketching schemes are equivalent to one-round protocols in the broadcast congested clique model. We prove that the expected average message length must be at least Ω(log3 n) bits, if the error probability is at most 1/4. It matches the upper bound obtained by the AGM sketch [AGM12], which even allows the referee to output a spanning forest of G with probability 1 − 1/poly n. Our lower bound strengthens the previous Ω(log3 n) lower bound for spanning forest computation [NY19]. Hence, it implies that connectivity, a decision problem, is as hard as its “search” version in this model.

Original languageEnglish (US)
Title of host publicationACM-SIAM Symposium on Discrete Algorithms, SODA 2021
EditorsDaniel Marx
PublisherAssociation for Computing Machinery
Pages1856-1873
Number of pages18
ISBN (Electronic)9781611976465
StatePublished - 2021
Event32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021 - Alexandria, Virtual, United States
Duration: Jan 10 2021Jan 13 2021

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Conference

Conference32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021
Country/TerritoryUnited States
CityAlexandria, Virtual
Period1/10/211/13/21

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint

Dive into the research topics of 'Tight distributed sketching lower bound for connectivity'. Together they form a unique fingerprint.

Cite this