article published yes Artur Czumaj author Peter Davies author 11396234-BB50-11E9-B24C-90FCE56974250000-0002-5646-9524 Merav Parter author DaAl department ISTplus - Postdoctoral Fellowships project We settle the complexity of the (∆ + 1)-coloring and (∆ + 1)-list coloring problems intheCONGESTED CLIQUEmodel by presenting a simpledeterministicalgorithm for both problemsrunning in a constant number of rounds. This matches the complexity of the recent breakthroughrandomizedconstant-round (∆ + 1)-list coloring algorithm due to Chang et al. [Proceedings of the38th ACM Symposium on Principles of Distributed Computing, 2019] and significantly improvesupon the state-of-the-artO(log ∆)-round deterministic (∆ + 1)-coloring bound of Parter [Proceed-ings of the 45th Annual International Colloquium on Automata, Languages and Programming]. Aremarkable property of our algorithm is its simplicity. Whereas the state-of-the-artrandomizedal-gorithms for this problem are based on the quite involved local coloring algorithm of Chang, Li, andPettie [Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018],our algorithm can be described in just a few lines. At a high level, it applies a careful derandomiza-tion of a recursive procedure which partitions the nodes and their respective palettes into separatebins. We show that afterO(1) recursion steps, the remaining uncolored subgraph within each bin haslinear size and thus can be solved locally by collecting it to a single node. This algorithm can alsobe implemented in the massively parallel computation (MPC) model provided that each machine haslinear (inn, the number of nodes in the input graph) space. We also show an extension of our algo-rithm to theMPCregime, in which machines havesublinearspace: we present the first deterministic(∆ + 1)-list coloring algorithm designed for sublinear-spaceMPC, which runs inO(log ∆ + log logn)rounds. Society for Industrial and Applied Mathematics2021 eng General MathematicsGeneral Computer Science 0097-5397 1095-7111 00071300860000410.1137/20m1366502 5051603-1626 A. Czumaj, P. Davies, and M. Parter, “Simple, deterministic, constant-round coloring in congested clique and MPC,” <i>SIAM Journal on Computing</i>, vol. 50, no. 5. Society for Industrial and Applied Mathematics, pp. 1603–1626, 2021. Czumaj, A., Davies, P., &#38; Parter, M. (2021). Simple, deterministic, constant-round coloring in congested clique and MPC. <i>SIAM Journal on Computing</i>. Society for Industrial and Applied Mathematics. <a href="https://doi.org/10.1137/20m1366502">https://doi.org/10.1137/20m1366502</a> Czumaj A, Davies P, Parter M. 2021. Simple, deterministic, constant-round coloring in congested clique and MPC. SIAM Journal on Computing. 50(5), 1603–1626. A. Czumaj, P. Davies, M. Parter, SIAM Journal on Computing 50 (2021) 1603–1626. Czumaj A, Davies P, Parter M. Simple, deterministic, constant-round coloring in congested clique and MPC. <i>SIAM Journal on Computing</i>. 2021;50(5):1603-1626. doi:<a href="https://doi.org/10.1137/20m1366502">10.1137/20m1366502</a> Czumaj, Artur, Peter Davies, and Merav Parter. “Simple, Deterministic, Constant-Round Coloring in Congested Clique and MPC.” <i>SIAM Journal on Computing</i>. Society for Industrial and Applied Mathematics, 2021. <a href="https://doi.org/10.1137/20m1366502">https://doi.org/10.1137/20m1366502</a>. Czumaj, Artur, et al. “Simple, Deterministic, Constant-Round Coloring in Congested Clique and MPC.” <i>SIAM Journal on Computing</i>, vol. 50, no. 5, Society for Industrial and Applied Mathematics, 2021, pp. 1603–26, doi:<a href="https://doi.org/10.1137/20m1366502">10.1137/20m1366502</a>. 152712024-04-03T07:53:22Z2025-09-10T10:14:11Z