---
res:
bibo_abstract:
- "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].@eng"
bibo_authorlist:
- foaf_Person:
foaf_givenName: Artur
foaf_name: Czumaj, Artur
foaf_surname: Czumaj
orcid: 0000-0002-5646-9524
- foaf_Person:
foaf_givenName: Peter
foaf_name: Davies, Peter
foaf_surname: Davies
foaf_workInfoHomepage: http://www.librecat.org/personId=11396234-BB50-11E9-B24C-90FCE5697425
orcid: 0000-0002-5646-9524
- foaf_Person:
foaf_givenName: Merav
foaf_name: Parter, Merav
foaf_surname: Parter
dct_date: 2020^xs_gYear
dct_language: eng
dct_publisher: Association for Computing Machinery@
dct_title: Graph sparsification for derandomizing massively parallel computation
with low space@
...