English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

We settle the complexity of the $(\Delta+1)$-coloring and $(\Delta+1)$-listcoloring problems in the CONGESTED CLIQUE model by presenting a simpledeterministic algorithm for both problems running in a constant number ofrounds. This matches the complexity of the recent breakthrough randomizedconstant-round $(\Delta+1)$-list coloring algorithm due to Chang et al.(PODC'19), and significantly improves upon the state-of-the-art $O(\log\Delta)$-round deterministic $(\Delta+1)$-coloring bound of Parter (ICALP'18).  A remarkable property of our algorithm is its simplicity. Whereas thestate-of-the-art randomized algorithms for this problem are based on the quiteinvolved local coloring algorithm of Chang et al. (STOC'18), our algorithm canbe described in just a few lines. At a high level, it applies a carefulderandomization of a recursive procedure which partitions the nodes and theirrespective palettes into separate bins. We show that after $O(1)$ recursionsteps, the remaining uncolored subgraph within each bin has linear size, andthus can be solved locally by collecting it to a single node. This algorithmcan also be implemented in the Massively Parallel Computation (MPC) modelprovided that each machine has linear (in $n$, the number of nodes in the inputgraph) space.  We also show an extension of our algorithm to the MPC regime in whichmachines have sublinear space: we present the first deterministic$(\Delta+1)$-list coloring algorithm designed for sublinear-space MPC, whichruns in $O(\log \Delta + \log\log n)$ rounds.

Simple, Deterministic, Constant-Round Coloring in the Congested Clique