Algebraic methods in the congested clique

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

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

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 (Formula presented.) round matrix multiplication algorithm, where (Formula presented.) 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:1.triangle and 4-cycle counting in (Formula presented.) rounds, improving upon the (Formula presented.) algorithm of Dolev et al. [DISC 2012],2.a (Formula presented.)-approximation of all-pairs shortest paths in (Formula presented.) rounds, improving upon the (Formula presented.)-round (Formula presented.)-approximation algorithm given by Nanongkai [STOC 2014], and3.computing the girth in (Formula presented.) 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.

Original languageEnglish
Pages (from-to)461-478
Number of pages18
JournalDISTRIBUTED COMPUTING
Volume32
Issue number6
Early online date19 Mar 2016
DOIs
Publication statusPublished - 2019
MoE publication typeA1 Journal article-refereed

Keywords

  • Congested clique model
  • Distance computation
  • Distributed computing
  • Lower bounds
  • Matrix multiplication
  • Subgraph detection

Fingerprint Dive into the research topics of 'Algebraic methods in the congested clique'. Together they form a unique fingerprint.

  • Cite this