# Problem 65: Communication Complexity of Connectivity

From Open Problems in Sublinear Algorithms

Suggested by | Andrew McGregor |
---|---|

Source | Bertinoro 2014 |

Short link | https://sublinear.info/65 |

A recent result in graph sketching [AhnGM-12] can be rephrased in terms of a simultaneous message communication protocol with public coins. Specifically, suppose that $n$ players are each given a row of the adjacency matrix of some graph. The players simultaneously send a message to a central player who must then determine whether the graph is connected. Existing work shows that this is possible with $O(\log^3 n)$ bit messages from each player. Are $O(\log^2 n)$ or $O(\log n)$ bits sufficient? Also, is there a non-trivial lower bound if the players must use private coins?