Brief announcement: Deterministic graph connectivity in the broadcast congested clique

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. Specifi- cally, we exhibit a deterministic protocol that computes the connected components of the input graph in [1/ϵ] rounds, each player communicating O(n^ϵ · log n) bits per round, with 0 < ϵ ≤ 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 O(n^1/r · 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.