---
res:
bibo_abstract:
- "We design fast deterministic algorithms for distance computation in the CONGESTED
CLIQUE model. Our key contributions include:\r\n\r\n - A (2+ε)-approximation for
all-pairs shortest paths problem in O(log²n / ε) rounds on unweighted undirected
graphs. With a small additional additive factor, this also applies for weighted
graphs. This is the first sub-polynomial constant-factor approximation for APSP
in this model.\r\n - A (1+ε)-approximation for multi-source shortest paths problem
from O(√n) sources in O(log² n / ε) rounds on weighted undirected graphs. This
is the first sub-polynomial algorithm obtaining this approximation for a set of
sources of polynomial size.\r\n\r\nOur main techniques are new distance tools
that are obtained via improved algorithms for sparse matrix multiplication, which
we leverage to construct efficient hopsets and shortest paths. Furthermore, our
techniques extend to additional distance problems for which we improve upon the
state-of-the-art, including diameter approximation, and an exact single-source
shortest paths algorithm for weighted undirected graphs in Õ(n^{1/6}) rounds.@eng"
bibo_authorlist:
- foaf_Person:
foaf_givenName: Keren
foaf_name: Censor-Hillel, Keren
foaf_surname: Censor-Hillel
- foaf_Person:
foaf_givenName: Michal
foaf_name: Dory, Michal
foaf_surname: Dory
- 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: Dean
foaf_name: Leitersdorf, Dean
foaf_surname: Leitersdorf
bibo_doi: 10.1145/3293611.3331633
dct_date: 2019^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/9781450362177
dct_language: eng
dct_publisher: ACM@
dct_title: Fast approximate shortest paths in the congested clique@
...