---
res:
  bibo_abstract:
  - "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.@eng"
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Artur
      foaf_name: Czumaj, Artur
      foaf_surname: Czumaj
    orcid: 0000-0002-5646-9524
  - 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.1145/3382734.3405751
  dct_date: 2020^xs_gYear
  dct_identifier:
  - UT:001436693500042
  dct_language: eng
  dct_publisher: Association for Computing Machinery@
  dct_title: Simple, deterministic, constant-round coloring in the congested clique@
...