Faster Cycle Detection in the Congested Clique

We provide a fast distributed algorithm for detecting h-cycles in the Congested Clique model, whose running time decreases as the number of h-cycles in the graph increases. In undirected graphs, constant-round algorithms are known for cycles of even length. Our algorithm greatly improves upon the state of the art for odd values of h. Moreover, our running time applies also to directed graphs, in which case the improvement is for all values of h. Further, our techniques allow us to obtain a triangle detection algorithm in the quantum variant of this model, which is faster than prior work. A key technical contribution we develop to obtain our fast cycle detection algorithm is a new algorithm for computing the product of many pairs of small matrices in parallel, which may be of independent interest.