---
_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
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. ACM Transactions on Algorithms. 2021;17(2).
doi:10.1145/3451992
apa: Czumaj, A., Davies, P., & Parter, M. (2021). Graph sparsification for derandomizing
massively parallel computation with low space. ACM Transactions on Algorithms.
Association for Computing Machinery. https://doi.org/10.1145/3451992
chicago: Czumaj, Artur, Peter Davies, and Merav Parter. “Graph Sparsification for
Derandomizing Massively Parallel Computation with Low Space.” ACM Transactions
on Algorithms. Association for Computing Machinery, 2021. https://doi.org/10.1145/3451992.
ieee: A. Czumaj, P. Davies, and M. Parter, “Graph sparsification for derandomizing
massively parallel computation with low space,” ACM Transactions on Algorithms,
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.” ACM Transactions on Algorithms, vol. 17, no.
2, 16, Association for Computing Machinery, 2021, doi:10.1145/3451992.
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: 2024-02-28T12:53:09Z
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
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'
...