Tight Distributed Sketching Lower Bound for Connectivity

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 Ω(log 3 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 Ω(log 3 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.