---
_id: '15271'
abstract:
- lang: eng
  text: '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.'
acknowledgement: The  first  author  was  partially  supported  by  the  Centre  for  Discrete  Mathematics
  and its Applications, by the IBM Faculty Award, and by the EPSRC award EP/N011163/1.  The
  second author was partially supported by the European Union’s Horizon 2020 research
  and innovation program under the Marie Sklodowska-Curie grant agreement 754411.  The
  first and third authors were partially supported by a Weizmann-UK Making Connections
  grant.
article_processing_charge: No
article_type: original
author:
- first_name: Artur
  full_name: Czumaj, Artur
  last_name: Czumaj
- 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. 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>
  apa: 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>
  chicago: 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>.
  ieee: 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.
  ista: 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.
  mla: 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>.
  short: A. Czumaj, P. Davies, M. Parter, SIAM Journal on Computing 50 (2021) 1603–1626.
date_created: 2024-04-03T07:53:22Z
date_published: 2021-01-01T00:00:00Z
date_updated: 2025-09-10T10:14:11Z
day: '01'
department:
- _id: DaAl
doi: 10.1137/20m1366502
ec_funded: 1
external_id:
  isi:
  - '000713008600004'
intvolume: '        50'
isi: 1
issue: '5'
keyword:
- General Mathematics
- General Computer Science
language:
- iso: eng
month: '01'
oa_version: None
page: 1603-1626
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '754411'
  name: ISTplus - Postdoctoral Fellowships
publication: SIAM Journal on Computing
publication_identifier:
  eissn:
  - 1095-7111
  issn:
  - 0097-5397
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
scopus_import: '1'
status: public
title: Simple, deterministic, constant-round coloring in congested clique and MPC
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 50
year: '2021'
...