Deterministic graph connectivity in the broadcast congested clique
Pedro Montealegre, Ioan Todinca · arXiv (Cornell University) · 2016
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/ε\rceil$ rounds, each player communicating $\mathcal{O}(n^ε \cdot \log n)$ bits per round, with $0 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.