---
_id: '9541'
abstract:
- lang: eng
  text: The Massively Parallel Computation (MPC) model is an emerging model that distills
    core aspects of distributed and parallel computation, developed as a tool to solve
    combinatorial (typically graph) problems in systems of many machines with limited
    space. Recent work has focused on the regime in which machines have sublinear
    (in n, the number of nodes in the input graph) space, with randomized algorithms
    presented for the fundamental problems of Maximal Matching and Maximal Independent
    Set. However, there have been no prior corresponding deterministic algorithms.
    A major challenge underlying the sublinear space setting is that the local space
    of each machine might be too small to store all edges incident to a single node.
    This poses a considerable obstacle compared to classical models in which each
    node is assumed to know and have easy access to its incident edges. To overcome
    this barrier, we introduce a new graph sparsification technique that deterministically
    computes a low-degree subgraph, with the additional property that solving the
    problem on this subgraph provides significant progress towards solving the problem
    for the original input graph. Using this framework to derandomize the well-known
    algorithm of Luby [SICOMP’86], we obtain O(log Δ + log log n)-round deterministic
    MPC algorithms for solving the problems of Maximal Matching and Maximal Independent
    Set with O(nɛ) space on each machine for any constant ɛ > 0. These algorithms
    also run in O(log Δ) rounds in the closely related model of CONGESTED CLIQUE,
    improving upon the state-of-the-art bound of O(log 2Δ) rounds by Censor-Hillel
    et al. [DISC’17].
acknowledgement: "Institute of Science and Technology Austria (IST Austria). Email:
  peter.davies@ist.ac.at. Work partially\r\ndone at the Department of Computer Science
  and Centre for Discrete Mathematics and its Applications (DIMAP),University of Warwick.
  Research partially supported by the European Union’s Horizon 2020 research and innovation
  programme under the Marie Skłodowska-Curie grant agreement No 754411, the Centre
  for Discrete Mathematics and its Applications, a Weizmann-UK Making Connections
  Grant, and EPSRC award EP/N011163/1."
article_number: '16'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Artur
  full_name: Czumaj, Artur
  last_name: Czumaj
- first_name: Peter
  full_name: Davies, Peter
  id: 11396234-BB50-11E9-B24C-90FCE5697425
  last_name: Davies
  orcid: 0000-0002-5646-9524
- first_name: Merav
  full_name: Parter, Merav
  last_name: Parter
citation:
  ama: Czumaj A, Davies P, Parter M. Graph sparsification for derandomizing massively
    parallel computation with low space. <i>ACM Transactions on Algorithms</i>. 2021;17(2).
    doi:<a href="https://doi.org/10.1145/3451992">10.1145/3451992</a>
  apa: Czumaj, A., Davies, P., &#38; Parter, M. (2021). Graph sparsification for derandomizing
    massively parallel computation with low space. <i>ACM Transactions on Algorithms</i>.
    Association for Computing Machinery. <a href="https://doi.org/10.1145/3451992">https://doi.org/10.1145/3451992</a>
  chicago: Czumaj, Artur, Peter Davies, and Merav Parter. “Graph Sparsification for
    Derandomizing Massively Parallel Computation with Low Space.” <i>ACM Transactions
    on Algorithms</i>. Association for Computing Machinery, 2021. <a href="https://doi.org/10.1145/3451992">https://doi.org/10.1145/3451992</a>.
  ieee: A. Czumaj, P. Davies, and M. Parter, “Graph sparsification for derandomizing
    massively parallel computation with low space,” <i>ACM Transactions on Algorithms</i>,
    vol. 17, no. 2. Association for Computing Machinery, 2021.
  ista: Czumaj A, Davies P, Parter M. 2021. Graph sparsification for derandomizing
    massively parallel computation with low space. ACM Transactions on Algorithms.
    17(2), 16.
  mla: Czumaj, Artur, et al. “Graph Sparsification for Derandomizing Massively Parallel
    Computation with Low Space.” <i>ACM Transactions on Algorithms</i>, vol. 17, no.
    2, 16, Association for Computing Machinery, 2021, doi:<a href="https://doi.org/10.1145/3451992">10.1145/3451992</a>.
  short: A. Czumaj, P. Davies, M. Parter, ACM Transactions on Algorithms 17 (2021).
date_created: 2021-06-10T19:31:05Z
date_published: 2021-06-01T00:00:00Z
date_updated: 2025-04-15T06:54:47Z
day: '01'
ddc:
- '000'
department:
- _id: DaAl
doi: 10.1145/3451992
ec_funded: 1
external_id:
  arxiv:
  - '1912.05390'
  isi:
  - '000661311300006'
file:
- access_level: open_access
  checksum: a21c627683890c309a68f6389302c408
  content_type: application/pdf
  creator: pdavies
  date_created: 2021-06-10T19:33:56Z
  date_updated: 2021-06-10T19:33:56Z
  file_id: '9542'
  file_name: MISMM-arxiv.pdf
  file_size: 587404
  relation: main_file
  success: 1
file_date_updated: 2021-06-10T19:33:56Z
has_accepted_license: '1'
intvolume: '        17'
isi: 1
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1912.05390
month: '06'
oa: 1
oa_version: Submitted Version
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '754411'
  name: ISTplus - Postdoctoral Fellowships
publication: ACM Transactions on Algorithms
publication_identifier:
  eissn:
  - 1549-6333
  issn:
  - 1549-6325
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
related_material:
  record:
  - id: '7802'
    relation: earlier_version
    status: public
scopus_import: '1'
status: public
title: Graph sparsification for derandomizing massively parallel computation with
  low space
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 17
year: '2021'
...