---
_id: '7802'
abstract:
- lang: eng
text: "The Massively Parallel Computation (MPC) model is an emerging model which
distills core aspects of distributed and parallel computation. It has been developed
as a tool to solve (typically graph) problems in systems where the input is distributed
over many machines with limited space.\r\n\t\r\nRecent 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 fundamental graph problems
of Maximal Matching and Maximal Independent Set. However, there have been no prior
corresponding deterministic algorithms.\r\n\t\r\n\tA major challenge underlying
the sublinear space setting is that the local space of each machine might be too
small to store all the edges incident to a single node. This poses a considerable
obstacle compared to the 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 additional desired properties. The degree of the nodes in this subgraph
is small in the sense that the edges of each node can be now stored on a single
machine. This low-degree subgraph also has the property that solving the problem
on this subgraph provides \\emph{significant} global progress, i.e., progress
towards solving the problem for the original input graph.\r\n\t\r\nUsing this
framework to derandomize the well-known randomized algorithm of Luby [SICOMP'86],
we obtain $O(\\log \\Delta+\\log\\log n)$-round deterministic MPC algorithms for
solving the fundamental problems of Maximal Matching and Maximal Independent Set
with $O(n^{\\epsilon})$ space on each machine for any constant $\\epsilon > 0$.
Based on the recent work of Ghaffari et al. [FOCS'18], this additive $O(\\log\\log
n)$ factor is conditionally essential. These algorithms can also be shown to run
in $O(\\log \\Delta)$ rounds in the closely related model of CONGESTED CLIQUE,
improving upon the state-of-the-art bound of $O(\\log^2 \\Delta)$ rounds by Censor-Hillel
et al. [DISC'17]."
article_processing_charge: No
author:
- first_name: Artur
full_name: Czumaj, Artur
last_name: Czumaj
orcid: 0000-0002-5646-9524
- 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. In: *Proceedings of the 32nd ACM Symposium
on Parallelism in Algorithms and Architectures (SPAA 2020)*. Association for
Computing Machinery; 2020:175-185. doi:10.1145/3350755.3400282'
apa: 'Czumaj, A., Davies, P., & Parter, M. (2020). Graph sparsification for
derandomizing massively parallel computation with low space. In *Proceedings
of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA
2020)* (pp. 175–185). Virtual Event, United States: Association for Computing
Machinery. https://doi.org/10.1145/3350755.3400282'
chicago: Czumaj, Artur, Peter Davies, and Merav Parter. “Graph Sparsification for
Derandomizing Massively Parallel Computation with Low Space.” In *Proceedings
of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA
2020)*, 175–85. Association for Computing Machinery, 2020. https://doi.org/10.1145/3350755.3400282.
ieee: A. Czumaj, P. Davies, and M. Parter, “Graph sparsification for derandomizing
massively parallel computation with low space,” in *Proceedings of the 32nd
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2020)*,
Virtual Event, United States, 2020, no. 7, pp. 175–185.
ista: 'Czumaj A, Davies P, Parter M. 2020. Graph sparsification for derandomizing
massively parallel computation with low space. Proceedings of the 32nd ACM Symposium
on Parallelism in Algorithms and Architectures (SPAA 2020). SPAA: Symposium on
Parallelism in Algorithms and Architectures, 175–185.'
mla: Czumaj, Artur, et al. “Graph Sparsification for Derandomizing Massively Parallel
Computation with Low Space.” *Proceedings of the 32nd ACM Symposium on Parallelism
in Algorithms and Architectures (SPAA 2020)*, no. 7, Association for Computing
Machinery, 2020, pp. 175–85, doi:10.1145/3350755.3400282.
short: A. Czumaj, P. Davies, M. Parter, in:, Proceedings of the 32nd ACM Symposium
on Parallelism in Algorithms and Architectures (SPAA 2020), Association for Computing
Machinery, 2020, pp. 175–185.
conference:
end_date: 2020-07-17
location: Virtual Event, United States
name: 'SPAA: Symposium on Parallelism in Algorithms and Architectures'
start_date: 2020-07-15
date_created: 2020-05-06T08:53:34Z
date_published: 2020-07-01T00:00:00Z
date_updated: 2021-06-16T12:46:59Z
day: '01'
department:
- _id: DaAl
doi: 10.1145/3350755.3400282
ec_funded: 1
external_id:
arxiv:
- '1912.05390'
issue: '7'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1912.05390
month: '07'
oa: 1
oa_version: Preprint
page: 175-185
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and
Architectures (SPAA 2020)
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
related_material:
record:
- id: '9541'
relation: later_version
status: public
scopus_import: '1'
status: public
title: Graph sparsification for derandomizing massively parallel computation with
low space
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2020'
...