Improved deterministic (Δ+1) coloring in low-space MPC

Czumaj A, Davies P, Parter M. 2021. Improved deterministic (Δ+1) coloring in low-space MPC. Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing. PODC: Symposium on Principles of Distributed Computing, 469–479.


Conference Paper | Published | English
Author
Czumaj, Artur; Davies, PeterISTA ; Parter, Merav
Department
Abstract
We present a deterministic O(log log log n)-round low-space Massively Parallel Computation (MPC) algorithm for the classical problem of (Δ+1)-coloring on n-vertex graphs. In this model, every machine has sublinear local space of size n^φ for any arbitrary constant φ \in (0,1). Our algorithm works under the relaxed setting where each machine is allowed to perform exponential local computations, while respecting the n^φ space and bandwidth limitations. Our key technical contribution is a novel derandomization of the ingenious (Δ+1)-coloring local algorithm by Chang-Li-Pettie (STOC 2018, SIAM J. Comput. 2020). The Chang-Li-Pettie algorithm runs in T_local =poly(loglog n) rounds, which sets the state-of-the-art randomized round complexity for the problem in the local model. Our derandomization employs a combination of tools, notably pseudorandom generators (PRG) and bounded-independence hash functions. The achieved round complexity of O(logloglog n) rounds matches the bound of log(T_local ), which currently serves an upper bound barrier for all known randomized algorithms for locally-checkable problems in this model. Furthermore, no deterministic sublogarithmic low-space MPC algorithms for the (Δ+1)-coloring problem have been known before.
Publishing Year
Date Published
2021-07-21
Proceedings Title
Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing
Acknowledgement
This work is partially supported by a Weizmann-UK Making Connections Grant, the Centre for Discrete Mathematics and its Applications (DIMAP), IBM Faculty Award, EPSRC award EP/V01305X/1, European Research Council (ERC) Grant No. 949083, the Minerva foundation with funding from the Federal German Ministry for Education and Research No. 713238, and the European Union’s Horizon 2020 programme under the Marie Skłodowska-Curie grant agreement No 754411.
Page
469–479
Conference
PODC: Symposium on Principles of Distributed Computing
Conference Location
Virtual, Italy
Conference Date
2021-07-26 – 2021-07-30
IST-REx-ID

Cite this

Czumaj A, Davies P, Parter M. Improved deterministic (Δ+1) coloring in low-space MPC. In: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing. Association for Computing Machinery; 2021:469–479. doi:10.1145/3465084.3467937
Czumaj, A., Davies, P., & Parter, M. (2021). Improved deterministic (Δ+1) coloring in low-space MPC. In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing (pp. 469–479). Virtual, Italy: Association for Computing Machinery. https://doi.org/10.1145/3465084.3467937
Czumaj, Artur, Peter Davies, and Merav Parter. “Improved Deterministic (Δ+1) Coloring in Low-Space MPC.” In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, 469–479. Association for Computing Machinery, 2021. https://doi.org/10.1145/3465084.3467937.
A. Czumaj, P. Davies, and M. Parter, “Improved deterministic (Δ+1) coloring in low-space MPC,” in Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, Virtual, Italy, 2021, pp. 469–479.
Czumaj A, Davies P, Parter M. 2021. Improved deterministic (Δ+1) coloring in low-space MPC. Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing. PODC: Symposium on Principles of Distributed Computing, 469–479.
Czumaj, Artur, et al. “Improved Deterministic (Δ+1) Coloring in Low-Space MPC.” Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2021, pp. 469–479, doi:10.1145/3465084.3467937.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data ISTA Research Explorer

Search this title in

Google Scholar
ISBN Search