What Can We Compute in a Single Round of the Congested Clique?

We study the computational power of one-round distributed algorithms in the congested clique model. We show that any one-round algorithm that computes a minimum spanning tree (MST) in the unicast congested clique must use a link bandwidth of $\Omega(\log^3 n)$ bits in the worst case. This is the first round complexity lower bound in the unicast congested clique for a problem where the output size is small, i.e., $O(n\log n)$ bits. Our main technical contribution is to investigate one-round algorithms in the broadcast congested clique and, equivalently, the distributed graph sketching model where the nodes send their message to a referee who computes the output. First, we present a tight lower bound of $\Omega(n)$ bits for the message size of computing a breadth-first search tree. Then, we prove that computing a $k$-edge connected spanning subgraph ($k$-ECSS) requires messages of size at least $\Omega \left( k\log^2(n/k) \right)$. We also show that verifying whether a given vertex coloring forms a weak 2-coloring of the input graph requires messages of $\Omega(n^{1/3}\log^{2/3}n)$ bits, and the same lower bound holds for verifying whether a subset of nodes forms a maximal independent set or a minimal dominating set. Interestingly, it turns out that the same class of lower bound graphs for the distributed sketching model is versatile enough to yield a space lower bound of $\Omega(n^2)$ bits for verifying symmetry breaking problems such as weak $2$-coloring in the fully dynamic turnstile model, where the input arrives as a stream of edges. We also (nearly) settle the space complexity of the $k$-ECSS problem in the streaming model by extending the work of Kapralov et al. (FOCS 2017): We prove a communication complexity lower bound for a direct sum variant of the $\text{UR}_k^{\subset}$ problem and show that this implies $\Omega(k\,n\log^2(n/k))$ bits of memory for computing a $k$-ECSS.