TY - GEN

T1 - Lower Bounds for Distributed Sketching of Maximal Matchings and Maximal Independent Sets

AU - Assadi, Sepehr

AU - Kol, Gillat

AU - Oshman, Rotem

N1 - Publisher Copyright:
© 2020 ACM.

PY - 2020/7/31

Y1 - 2020/7/31

N2 - Consider the following distributed graph sketching model: There is a referee and n vertices in an undirected graph G sharing public randomness. Each vertex v only knows its neighborhood in G and the referee receives no input initially. The vertices simultaneously each sends a message, called a sketch, to the referee who then based on the received sketches outputs a solution to some combinatorial problem on G, say, the minimum spanning tree problem. Previous work on graph sketching have shown that numerous problems, including connectivity, minimum spanning tree, edge or vertex connectivity, cut or spectral sparsifiers, and (Δ + 1)-vertex coloring, all admit efficient algorithms in this model that only require sketches of size polylog(n) per vertex. In contrast, we prove that the two fundamental problems of maximal matching and maximal independent set do not admit such efficient solutions: Any algorithm for either problem that errs with a small constant probability requires sketches of size Ω(n1/2 - ϵ) for any constant ϵ > 0. We prove our results by analyzing communication complexity of these problems in a communication model that allows sharing of inputs between limited number of players, and hence lies between the standard number-in-hand and number-on-forehead multi-party communication models. Our proofs are based on a family of hard instances using Ruzsa-Szemerédi graphs and information-theoretic arguments to establish the communication lower bounds.

AB - Consider the following distributed graph sketching model: There is a referee and n vertices in an undirected graph G sharing public randomness. Each vertex v only knows its neighborhood in G and the referee receives no input initially. The vertices simultaneously each sends a message, called a sketch, to the referee who then based on the received sketches outputs a solution to some combinatorial problem on G, say, the minimum spanning tree problem. Previous work on graph sketching have shown that numerous problems, including connectivity, minimum spanning tree, edge or vertex connectivity, cut or spectral sparsifiers, and (Δ + 1)-vertex coloring, all admit efficient algorithms in this model that only require sketches of size polylog(n) per vertex. In contrast, we prove that the two fundamental problems of maximal matching and maximal independent set do not admit such efficient solutions: Any algorithm for either problem that errs with a small constant probability requires sketches of size Ω(n1/2 - ϵ) for any constant ϵ > 0. We prove our results by analyzing communication complexity of these problems in a communication model that allows sharing of inputs between limited number of players, and hence lies between the standard number-in-hand and number-on-forehead multi-party communication models. Our proofs are based on a family of hard instances using Ruzsa-Szemerédi graphs and information-theoretic arguments to establish the communication lower bounds.

KW - broadcast congested clique

KW - communication complexity

KW - distributed sketching

KW - maximal independent set

KW - maximal matching

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

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

U2 - 10.1145/3382734.3405732

DO - 10.1145/3382734.3405732

M3 - Conference contribution

AN - SCOPUS:85090362767

T3 - Proceedings of the Annual ACM Symposium on Principles of Distributed Computing

SP - 79

EP - 88

BT - PODC 2020 - Proceedings of the 39th Symposium on Principles of Distributed Computing

PB - Association for Computing Machinery

T2 - 39th Symposium on Principles of Distributed Computing, PODC 2020

Y2 - 3 August 2020 through 7 August 2020

ER -