  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
$\Omega(\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/\mathrm{poly}\, n$. Our lower bound strengthens the previous
$\Omega(\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.
