---
_id: '7803'
abstract:
- lang: eng
  text: "We settle the complexity of the (Δ+1)-coloring and (Δ+1)-list coloring problems
    in the CONGESTED CLIQUE model by presenting a simple deterministic algorithm for
    both problems running in a constant number of rounds. This matches the complexity
    of the recent breakthrough randomized constant-round (Δ+1)-list coloring algorithm
    due to Chang et al. (PODC'19), and significantly improves upon the state-of-the-art
    O(logΔ)-round deterministic (Δ+1)-coloring bound of Parter (ICALP'18).\r\nA remarkable
    property of our algorithm is its simplicity. Whereas the state-of-the-art randomized
    algorithms for this problem are based on the quite involved local coloring algorithm
    of Chang et al. (STOC'18), our algorithm can be described in just a few lines.
    At a high level, it applies a careful derandomization of a recursive procedure
    which partitions the nodes and their respective palettes into separate bins. We
    show that after O(1) recursion steps, the remaining uncolored subgraph within
    each bin has linear size, and thus can be solved locally by collecting it to a
    single node. This algorithm can also be implemented in the Massively Parallel
    Computation (MPC) model provided that each machine has linear (in n, the number
    of nodes in the input graph) space.\r\nWe also show an extension of our algorithm
    to the MPC regime in which machines have sublinear space: we present the first
    deterministic (Δ+1)-list coloring algorithm designed for sublinear-space MPC,
    which runs in O(logΔ+loglogn) rounds."
article_processing_charge: No
arxiv: 1
author:
- first_name: Artur
  full_name: Czumaj, Artur
  last_name: Czumaj
  orcid: 0000-0002-5646-9524
- 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 the congested clique. In: <i>Proceedings of the 2020 ACM Symposium on Principles
    of Distributed Computing</i>. Association for Computing Machinery; 2020:309-318.
    doi:<a href="https://doi.org/10.1145/3382734.3405751">10.1145/3382734.3405751</a>'
  apa: 'Czumaj, A., Davies, P., &#38; Parter, M. (2020). Simple, deterministic, constant-round
    coloring in the congested clique. In <i>Proceedings of the 2020 ACM Symposium
    on Principles of Distributed Computing</i> (pp. 309–318). Salerno, Italy: Association
    for Computing Machinery. <a href="https://doi.org/10.1145/3382734.3405751">https://doi.org/10.1145/3382734.3405751</a>'
  chicago: Czumaj, Artur, Peter Davies, and Merav Parter. “Simple, Deterministic,
    Constant-Round Coloring in the Congested Clique.” In <i>Proceedings of the 2020
    ACM Symposium on Principles of Distributed Computing</i>, 309–18. Association
    for Computing Machinery, 2020. <a href="https://doi.org/10.1145/3382734.3405751">https://doi.org/10.1145/3382734.3405751</a>.
  ieee: A. Czumaj, P. Davies, and M. Parter, “Simple, deterministic, constant-round
    coloring in the congested clique,” in <i>Proceedings of the 2020 ACM Symposium
    on Principles of Distributed Computing</i>, Salerno, Italy, 2020, pp. 309–318.
  ista: 'Czumaj A, Davies P, Parter M. 2020. Simple, deterministic, constant-round
    coloring in the congested clique. Proceedings of the 2020 ACM Symposium on Principles
    of Distributed Computing. PODC: Symposium on Principles of Distributed Computing,
    309–318.'
  mla: Czumaj, Artur, et al. “Simple, Deterministic, Constant-Round Coloring in the
    Congested Clique.” <i>Proceedings of the 2020 ACM Symposium on Principles of Distributed
    Computing</i>, Association for Computing Machinery, 2020, pp. 309–18, doi:<a href="https://doi.org/10.1145/3382734.3405751">10.1145/3382734.3405751</a>.
  short: A. Czumaj, P. Davies, M. Parter, in:, Proceedings of the 2020 ACM Symposium
    on Principles of Distributed Computing, Association for Computing Machinery, 2020,
    pp. 309–318.
conference:
  end_date: 2020-08-07
  location: Salerno, Italy
  name: 'PODC: Symposium on Principles of Distributed Computing'
  start_date: 2020-08-03
date_created: 2020-05-06T09:02:14Z
date_published: 2020-07-01T00:00:00Z
date_updated: 2025-09-10T10:18:18Z
day: '01'
ddc:
- '000'
department:
- _id: DaAl
doi: 10.1145/3382734.3405751
ec_funded: 1
external_id:
  arxiv:
  - '2009.06043'
  isi:
  - '001436693500042'
file:
- access_level: open_access
  checksum: 46fe4fc58a64eb04068115573f631d4c
  content_type: application/pdf
  creator: pdavies
  date_created: 2020-10-08T08:17:36Z
  date_updated: 2020-10-08T08:17:36Z
  file_id: '8624'
  file_name: ColoringArxiv.pdf
  file_size: 520051
  relation: main_file
  success: 1
file_date_updated: 2020-10-08T08:17:36Z
fulldoi: https://doi.org/10.1145/3382734.3405751
has_accepted_license: '1'
isi: 1
language:
- iso: eng
month: '07'
oa: 1
oa_version: Submitted Version
page: 309-318
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '754411'
  name: ISTplus - Postdoctoral Fellowships
publication: Proceedings of the 2020 ACM Symposium on Principles of Distributed Computing
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: Simple, deterministic, constant-round coloring in the congested clique
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
year: '2020'
...