---
res:
  bibo_abstract:
  - '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.@eng'
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Artur
      foaf_name: Czumaj, Artur
      foaf_surname: Czumaj
  - foaf_Person:
      foaf_givenName: Peter
      foaf_name: Davies, Peter
      foaf_surname: Davies
      foaf_workInfoHomepage: http://www.librecat.org/personId=11396234-BB50-11E9-B24C-90FCE5697425
    orcid: 0000-0002-5646-9524
  - foaf_Person:
      foaf_givenName: Merav
      foaf_name: Parter, Merav
      foaf_surname: Parter
  bibo_doi: 10.1137/20m1366502
  bibo_issue: '5'
  bibo_volume: 50
  dct_date: 2021^xs_gYear
  dct_identifier:
  - UT:000713008600004
  dct_isPartOf:
  - http://id.crossref.org/issn/0097-5397
  - http://id.crossref.org/issn/1095-7111
  dct_language: eng
  dct_publisher: Society for Industrial and Applied Mathematics@
  dct_subject:
  - General Mathematics
  - General Computer Science
  dct_title: Simple, deterministic, constant-round coloring in congested clique and
    MPC@
...