Faster Cycle Detection in the Congested Clique
<|reference_start|>Faster Cycle Detection in the Congested Clique: 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.<|reference_end|>
@article{censor-hillel2024faster,
    title={Faster Cycle Detection in the Congested Clique},
    author={Keren Censor-Hillel, Tomer Even and Virginia Vassilevska Williams},
    journal={arXiv preprint arXiv:2408.15132},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.15132},
    primaryClass={cs.DS cs.DC}
}