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
U2 - 10.1137/1.9781611976465.111
DO - 10.1137/1.9781611976465.111
M3 - Conference contribution
AN - SCOPUS:85105355488
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 -