TY - GEN

T1 - Tight distributed sketching lower bound for connectivity

AU - Yu, Huacheng

N1 - Publisher Copyright: Copyright © 2021 by SIAM

PY - 2021

Y1 - 2021

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

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

UR - http://www.scopus.com/inward/record.url?scp=85105355488&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85105355488&partnerID=8YFLogxK

M3 - Conference contribution

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 1856

EP - 1873

BT - ACM-SIAM Symposium on Discrete Algorithms, SODA 2021

A2 - Marx, Daniel

PB - Association for Computing Machinery

T2 - 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021

Y2 - 10 January 2021 through 13 January 2021

ER -