Distributed Computing · volume 32, issue 6, pages 461–478, 2019 · doi:10.1007/s00446-016-0270-2
In this work, we use algebraic methods for studying distance computation and subgraph detection tasks in the congested clique model. Specifically, we adapt parallel matrix multiplication implementations to the congested clique, obtaining an $O(n^{1-2/\omega})$ round matrix multiplication algorithm, where $\omega < 2.3728639$ is the exponent of matrix multiplication. In conjunction with known techniques from centralised algorithmics, this gives significant improvements over previous best upper bounds in the congested clique model. The highlight results include:
In addition, we present a novel constant-round combinatorial algorithm for detecting 4-cycles.