1. Faster Cycle Detection in the Congested Clique
- Author
-
Censor-Hillel, Keren, Even, Tomer, and Williams, Virginia Vassilevska
- Subjects
Computer Science - Data Structures and Algorithms ,Computer Science - Distributed, Parallel, and Cluster Computing - Abstract
We provide a fast distributed algorithm for detecting $h$-cycles in the \textsf{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., Comment: 37 pages. To appear in proceedings of DISC 2024
- Published
- 2024