  We present deterministic constant-round protocols for the graph connectivity
problem in the model where each of the $n$ nodes of a graph receives a row of
the adjacency matrix, and broadcasts a single sublinear size message to all
other nodes. Communication rounds are synchronous. This model is sometimes
called the broadcast congested clique. Specifically, we exhibit a deterministic
protocol that computes the connected components of the input graph in $\lceil
1/\epsilon \rceil$ rounds, each player communicating $\mathcal{O}(n^{\epsilon}
\cdot \log n)$ bits per round, with $0 < \epsilon \leq 1$.
  We also provide a deterministic one-round protocol for connectivity, in the
model when each node receives as input the graph induced by the nodes at
distance at most $r>0$, and communicates $\mathcal{O}(n^{1/r} \cdot \log n)$
bits. This result is based on a $d$-pruning protocol, which consists in
successively removing nodes of degree at most $d$ until obtaining a graph with
minimum degree larger than $d$. Our technical novelty is the introduction of
deterministic sparse linear sketches: a linear compression function that
permits to recover sparse Boolean vectors deterministically.

Distributed, Parallel, and Cluster Computing;Data Structures and Algorithms