The Library
Deterministic massively parallel connectivity
Tools
Coy, Sam and Czumaj, Artur (2022) Deterministic massively parallel connectivity. In: ACM SIGACT Symposium on Theory of Computing (STOC ’22), Rome, Italy, 20-24 Jun. Published in: STOC 2022: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing pp. 162-175. ISBN 9781450392648. doi:10.1145/3519935.3520055
|
PDF
WRAP-Deterministic-massively-parallel-connectivity-Coy-2022.pdf - Accepted Version - Requires a PDF viewer. Download (841Kb) | Preview |
Official URL: https://doi.org/10.1145/3519935.3520055
Abstract
We consider the problem of designing fundamental graph algorithms on the model of Massive Parallel Computation (MPC). The input to the problem is an undirected graph G with n vertices and m edges, and with D being the maximum diameter of any connected component in G. We consider the MPC with low local space, allowing each machine to store only Θ(nδ) words for an arbitrary constant δ>0, and with linear global space (which is the number of machines times the local space available), that is, with optimal utilization.
In a recent breakthrough, Andoni et al. (FOCS’18) and Behnezhad et al. (FOCS’19) designed parallel randomized algorithms that in O(logD + loglogn) rounds on an MPC with low local space determine all connected components of a graph, improving on the classic bound of O(logn) derived from earlier works on PRAM algorithms.
In this paper, we show that asymptotically identical bounds can be also achieved for deterministic algorithms: we present a deterministic MPC low local space algorithm that in O(logD + loglogn) rounds determines connected components of the input graph. Our result matches the complexity of state of the art randomized algorithms for this task. The techniques developed in our paper can be also applied to several related problems, giving new deterministic MPC algorithms for problems like finding a spanning forest, minimum spanning forest, etc.
We complement our upper bounds by extending a recent lower bound for connectivity on an MPC conditioned on the 1-vs-2-cycles conjecture (which requires D ≥ log1+Ω(1)n), by showing a related conditional hardness of Ω(logD) MPC rounds for the entire spectrum of D, covering a particularly interesting range when D ≤ O(logn).
Item Type: | Conference Item (Paper) | ||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
||||||||||||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||||||||||||
Library of Congress Subject Headings (LCSH): | Machine theory, Computational complexity, Parallel algorithms , Numbers, Random, Computer science -- Mathematics, Graph algorithms, Computer algorithms, Graph connectivity | ||||||||||||||||||
Journal or Publication Title: | STOC 2022: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing | ||||||||||||||||||
Publisher: | ACM | ||||||||||||||||||
ISBN: | 9781450392648 | ||||||||||||||||||
Official Date: | 10 June 2022 | ||||||||||||||||||
Dates: |
|
||||||||||||||||||
Page Range: | pp. 162-175 | ||||||||||||||||||
DOI: | 10.1145/3519935.3520055 | ||||||||||||||||||
Status: | Peer Reviewed | ||||||||||||||||||
Publication Status: | Published | ||||||||||||||||||
Re-use Statement: | © 2022 Copyright held by the owner/author(s). Publication rights licensed to ACM. This is the author’s version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC ’22), June 20–24, 2022, Rome, Italy, https://doi.org/10.1145/3519935.3520055. | ||||||||||||||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||||||||||||||
Copyright Holders: | the owner/author(s). Publication rights licensed to ACM | ||||||||||||||||||
Date of first compliant deposit: | 19 April 2022 | ||||||||||||||||||
Date of first compliant Open Access: | 21 April 2022 | ||||||||||||||||||
RIOXX Funder/Project Grant: |
|
||||||||||||||||||
Conference Paper Type: | Paper | ||||||||||||||||||
Title of Event: | ACM SIGACT Symposium on Theory of Computing (STOC ’22) | ||||||||||||||||||
Type of Event: | Conference | ||||||||||||||||||
Location of Event: | Rome, Italy | ||||||||||||||||||
Date(s) of Event: | 20-24 Jun | ||||||||||||||||||
Related URLs: | |||||||||||||||||||
Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year