--- 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_identifier: - UT:000570442000011 dct_isPartOf: - http://id.crossref.org/issn/9781450362177 dct_language: eng dct_publisher: ACM@ dct_title: Fast approximate shortest paths in the congested clique@ ...