Keren Censor-Hillel · Petteri Kaski · Janne H. Korhonen · Christoph Lenzen · Ami Paz · Jukka Suomela

Algebraic methods in the congested clique

PODC 2015 · 34th Annual ACM Symposium on Principles of Distributed Computing, Donostia-San Sebastián, Spain, July 2015 · doi:10.1145/2767386.2767414

authors’ version publisher’s version arXiv.org

Abstract

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:

  • triangle and 4-cycle counting in $O(n^{0.158})$ rounds, improving upon the $O(n^{1/3})$ triangle counting algorithm of Dolev et al. [DISC 2012],
  • a $(1 + o(1))$-approximation of all-pairs shortest paths in $O(n^{0.158})$ rounds, improving upon the $\tilde{O} (n^{1/2})$-round $(2 + o(1))$-approximation algorithm of Nanongkai [STOC 2014], and
  • computing the girth in $O(n^{0.158})$ rounds, which is the first non-trivial solution in this model.

In addition, we present a novel constant-round combinatorial algorithm for detecting 4-cycles.

Publication

Chryssis Georgiou and Paul G. Spirakis (Eds.): PODC’15, Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, July 21–23, 2015, Donostia–San Sebastián, Spain, pages 143–152, ACM Press, New York, 2015

ISBN 978-1-4503-3617-8

Journal Version

This is the authors’ version of the work. It is posted here for your personal use. Not for redistribution. The definitive version was published in Proc. PODC 2015.

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.