---
_id: '7150'
abstract:
- lang: eng
  text: "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(n1−2/ω) round matrix multiplication algorithm, where ω<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:\r\n\r\n1.    triangle
    and 4-cycle counting in O(n0.158) rounds, improving upon the O(n1/3) algorithm
    of Dolev et al. [DISC 2012],\r\n2. a (1+o(1))-approximation of all-pairs shortest
    paths in O(n0.158) rounds, improving upon the O~(n1/2)-round (2+o(1))-approximation
    algorithm given by Nanongkai [STOC 2014], and\r\n 3. computing the girth in O(n0.158)
    rounds, which is the first non-trivial solution in this model.\r\n   \r\nIn addition,
    we present a novel constant-round combinatorial algorithm for detecting 4-cycles."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Keren
  full_name: Censor-Hillel, Keren
  last_name: Censor-Hillel
- first_name: Petteri
  full_name: Kaski, Petteri
  last_name: Kaski
- first_name: Janne
  full_name: Korhonen, Janne
  id: C5402D42-15BC-11E9-A202-CA2BE6697425
  last_name: Korhonen
- first_name: Christoph
  full_name: Lenzen, Christoph
  last_name: Lenzen
- first_name: Ami
  full_name: Paz, Ami
  last_name: Paz
- first_name: Jukka
  full_name: Suomela, Jukka
  last_name: Suomela
citation:
  ama: Censor-Hillel K, Kaski P, Korhonen J, Lenzen C, Paz A, Suomela J. Algebraic
    methods in the congested clique. <i>Distributed Computing</i>. 2019;32(6):461-478.
    doi:<a href="https://doi.org/10.1007/s00446-016-0270-2">10.1007/s00446-016-0270-2</a>
  apa: Censor-Hillel, K., Kaski, P., Korhonen, J., Lenzen, C., Paz, A., &#38; Suomela,
    J. (2019). Algebraic methods in the congested clique. <i>Distributed Computing</i>.
    Springer Nature. <a href="https://doi.org/10.1007/s00446-016-0270-2">https://doi.org/10.1007/s00446-016-0270-2</a>
  chicago: Censor-Hillel, Keren, Petteri Kaski, Janne Korhonen, Christoph Lenzen,
    Ami Paz, and Jukka Suomela. “Algebraic Methods in the Congested Clique.” <i>Distributed
    Computing</i>. Springer Nature, 2019. <a href="https://doi.org/10.1007/s00446-016-0270-2">https://doi.org/10.1007/s00446-016-0270-2</a>.
  ieee: K. Censor-Hillel, P. Kaski, J. Korhonen, C. Lenzen, A. Paz, and J. Suomela,
    “Algebraic methods in the congested clique,” <i>Distributed Computing</i>, vol.
    32, no. 6. Springer Nature, pp. 461–478, 2019.
  ista: Censor-Hillel K, Kaski P, Korhonen J, Lenzen C, Paz A, Suomela J. 2019. Algebraic
    methods in the congested clique. Distributed Computing. 32(6), 461–478.
  mla: Censor-Hillel, Keren, et al. “Algebraic Methods in the Congested Clique.” <i>Distributed
    Computing</i>, vol. 32, no. 6, Springer Nature, 2019, pp. 461–78, doi:<a href="https://doi.org/10.1007/s00446-016-0270-2">10.1007/s00446-016-0270-2</a>.
  short: K. Censor-Hillel, P. Kaski, J. Korhonen, C. Lenzen, A. Paz, J. Suomela, Distributed
    Computing 32 (2019) 461–478.
date_created: 2019-12-05T09:49:49Z
date_published: 2019-12-01T00:00:00Z
date_updated: 2021-01-12T08:12:05Z
day: '01'
doi: 10.1007/s00446-016-0270-2
extern: '1'
external_id:
  arxiv:
  - '1503.04963'
intvolume: '        32'
issue: '6'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1503.04963
month: '12'
oa: 1
oa_version: Preprint
page: 461-478
publication: Distributed Computing
publication_identifier:
  issn:
  - 0178-2770
  - 1432-0452
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
status: public
title: Algebraic methods in the congested clique
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 32
year: '2019'
...