---
_id: '6933'
abstract:
- lang: eng
  text: "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."
article_processing_charge: No
arxiv: 1
author:
- first_name: Keren
  full_name: Censor-Hillel, Keren
  last_name: Censor-Hillel
- first_name: Michal
  full_name: Dory, Michal
  last_name: Dory
- first_name: Janne
  full_name: Korhonen, Janne
  id: C5402D42-15BC-11E9-A202-CA2BE6697425
  last_name: Korhonen
- first_name: Dean
  full_name: Leitersdorf, Dean
  last_name: Leitersdorf
citation:
  ama: 'Censor-Hillel K, Dory M, Korhonen J, Leitersdorf D. Fast approximate shortest
    paths in the congested clique. In: <i>Proceedings of the 2019 ACM Symposium on
    Principles of Distributed Computin</i>. ACM; 2019:74-83. doi:<a href="https://doi.org/10.1145/3293611.3331633">10.1145/3293611.3331633</a>'
  apa: 'Censor-Hillel, K., Dory, M., Korhonen, J., &#38; Leitersdorf, D. (2019). Fast
    approximate shortest paths in the congested clique. In <i>Proceedings of the 2019
    ACM Symposium on Principles of Distributed Computin</i> (pp. 74–83). Toronto,
    ON, Canada: ACM. <a href="https://doi.org/10.1145/3293611.3331633">https://doi.org/10.1145/3293611.3331633</a>'
  chicago: Censor-Hillel, Keren, Michal Dory, Janne Korhonen, and Dean Leitersdorf.
    “Fast Approximate Shortest Paths in the Congested Clique.” In <i>Proceedings of
    the 2019 ACM Symposium on Principles of Distributed Computin</i>, 74–83. ACM,
    2019. <a href="https://doi.org/10.1145/3293611.3331633">https://doi.org/10.1145/3293611.3331633</a>.
  ieee: K. Censor-Hillel, M. Dory, J. Korhonen, and D. Leitersdorf, “Fast approximate
    shortest paths in the congested clique,” in <i>Proceedings of the 2019 ACM Symposium
    on Principles of Distributed Computin</i>, Toronto, ON, Canada, 2019, pp. 74–83.
  ista: 'Censor-Hillel K, Dory M, Korhonen J, Leitersdorf D. 2019. Fast approximate
    shortest paths in the congested clique. Proceedings of the 2019 ACM Symposium
    on Principles of Distributed Computin. PODC: Symposium on Principles of Distributed
    Computing, 74–83.'
  mla: Censor-Hillel, Keren, et al. “Fast Approximate Shortest Paths in the Congested
    Clique.” <i>Proceedings of the 2019 ACM Symposium on Principles of Distributed
    Computin</i>, ACM, 2019, pp. 74–83, doi:<a href="https://doi.org/10.1145/3293611.3331633">10.1145/3293611.3331633</a>.
  short: K. Censor-Hillel, M. Dory, J. Korhonen, D. Leitersdorf, in:, Proceedings
    of the 2019 ACM Symposium on Principles of Distributed Computin, ACM, 2019, pp.
    74–83.
conference:
  end_date: 2019-08-02
  location: Toronto, ON, Canada
  name: 'PODC: Symposium on Principles of Distributed Computing'
  start_date: 2019-07-29
date_created: 2019-10-08T12:48:42Z
date_published: 2019-08-01T00:00:00Z
date_updated: 2024-03-07T14:43:38Z
day: '01'
department:
- _id: DaAl
doi: 10.1145/3293611.3331633
external_id:
  arxiv:
  - '1903.05956'
  isi:
  - '000570442000011'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1903.05956
month: '08'
oa: 1
oa_version: Preprint
page: 74-83
publication: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computin
publication_identifier:
  isbn:
  - '9781450362177'
publication_status: published
publisher: ACM
quality_controlled: '1'
related_material:
  record:
  - id: '7939'
    relation: later_version
    status: public
scopus_import: '1'
status: public
title: Fast approximate shortest paths in the congested clique
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
year: '2019'
...
---
_id: '6935'
abstract:
- lang: eng
  text: "This paper investigates the power of preprocessing in the CONGEST model.
    Schmid and Suomela (ACM HotSDN 2013) introduced the SUPPORTED CONGEST model to
    study the application of distributed algorithms in Software-Defined Networks (SDNs).
    In this paper, we show that a large class of lower bounds in the CONGEST model
    still hold in the SUPPORTED model, highlighting the robustness of these bounds.
    This also raises the question how much does\r\npreprocessing help in the CONGEST
    model."
article_processing_charge: No
arxiv: 1
author:
- first_name: Klaus-Tycho
  full_name: Foerster, Klaus-Tycho
  last_name: Foerster
- first_name: Janne
  full_name: Korhonen, Janne
  id: C5402D42-15BC-11E9-A202-CA2BE6697425
  last_name: Korhonen
- first_name: Joel
  full_name: Rybicki, Joel
  id: 334EFD2E-F248-11E8-B48F-1D18A9856A87
  last_name: Rybicki
  orcid: 0000-0002-6432-6646
- first_name: Stefan
  full_name: Schmid, Stefan
  last_name: Schmid
citation:
  ama: 'Foerster K-T, Korhonen J, Rybicki J, Schmid S. Does preprocessing help under
    congestion? In: <i>Proceedings of the 2019 ACM Symposium on Principles of Distributed
    Computing</i>. ACM; 2019:259-261. doi:<a href="https://doi.org/10.1145/3293611.3331581">10.1145/3293611.3331581</a>'
  apa: 'Foerster, K.-T., Korhonen, J., Rybicki, J., &#38; Schmid, S. (2019). Does
    preprocessing help under congestion? In <i>Proceedings of the 2019 ACM Symposium
    on Principles of Distributed Computing</i> (pp. 259–261). Toronto, ON, Canada:
    ACM. <a href="https://doi.org/10.1145/3293611.3331581">https://doi.org/10.1145/3293611.3331581</a>'
  chicago: Foerster, Klaus-Tycho, Janne Korhonen, Joel Rybicki, and Stefan Schmid.
    “Does Preprocessing Help under Congestion?” In <i>Proceedings of the 2019 ACM
    Symposium on Principles of Distributed Computing</i>, 259–61. ACM, 2019. <a href="https://doi.org/10.1145/3293611.3331581">https://doi.org/10.1145/3293611.3331581</a>.
  ieee: K.-T. Foerster, J. Korhonen, J. Rybicki, and S. Schmid, “Does preprocessing
    help under congestion?,” in <i>Proceedings of the 2019 ACM Symposium on Principles
    of Distributed Computing</i>, Toronto, ON, Canada, 2019, pp. 259–261.
  ista: 'Foerster K-T, Korhonen J, Rybicki J, Schmid S. 2019. Does preprocessing help
    under congestion? Proceedings of the 2019 ACM Symposium on Principles of Distributed
    Computing. PODC: Symposium on Principles of Distributed Computing, 259–261.'
  mla: Foerster, Klaus-Tycho, et al. “Does Preprocessing Help under Congestion?” <i>Proceedings
    of the 2019 ACM Symposium on Principles of Distributed Computing</i>, ACM, 2019,
    pp. 259–61, doi:<a href="https://doi.org/10.1145/3293611.3331581">10.1145/3293611.3331581</a>.
  short: K.-T. Foerster, J. Korhonen, J. Rybicki, S. Schmid, in:, Proceedings of the
    2019 ACM Symposium on Principles of Distributed Computing, ACM, 2019, pp. 259–261.
conference:
  end_date: 2019-08-02
  location: Toronto, ON, Canada
  name: 'PODC: Symposium on Principles of Distributed Computing'
  start_date: 2019-07-29
date_created: 2019-10-08T12:57:14Z
date_published: 2019-08-01T00:00:00Z
date_updated: 2023-09-08T11:37:22Z
day: '01'
department:
- _id: DaAl
doi: 10.1145/3293611.3331581
ec_funded: 1
external_id:
  arxiv:
  - '1905.03012'
  isi:
  - '000570442000037'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1905.03012
month: '08'
oa: 1
oa_version: Preprint
page: 259-261
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '754411'
  name: ISTplus - Postdoctoral Fellowships
publication: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing
publication_identifier:
  isbn:
  - '9781450362177'
publication_status: published
publisher: ACM
quality_controlled: '1'
scopus_import: '1'
status: public
title: Does preprocessing help under congestion?
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2019'
...