---
res:
bibo_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(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.@eng"
bibo_authorlist:
- foaf_Person:
foaf_givenName: Keren
foaf_name: Censor-Hillel, Keren
foaf_surname: Censor-Hillel
- foaf_Person:
foaf_givenName: Petteri
foaf_name: Kaski, Petteri
foaf_surname: Kaski
- foaf_Person:
foaf_givenName: Janne
foaf_name: Korhonen, Janne
foaf_surname: Korhonen
foaf_workInfoHomepage: http://www.librecat.org/personId=C5402D42-15BC-11E9-A202-CA2BE6697425
- foaf_Person:
foaf_givenName: Christoph
foaf_name: Lenzen, Christoph
foaf_surname: Lenzen
- foaf_Person:
foaf_givenName: Ami
foaf_name: Paz, Ami
foaf_surname: Paz
- foaf_Person:
foaf_givenName: Jukka
foaf_name: Suomela, Jukka
foaf_surname: Suomela
bibo_doi: 10.1007/s00446-016-0270-2
bibo_issue: '6'
bibo_volume: 32
dct_date: 2019^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/0178-2770
- http://id.crossref.org/issn/1432-0452
dct_language: eng
dct_publisher: Springer Nature@
dct_title: Algebraic methods in the congested clique@
...