Abstract:
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 Ω(n^{1/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.
Conference version:
[PDF]