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

In this work, we develop the low-space Massively Parallel Computation (MPC)complexity landscape for a family of fundamental graph problems on trees. Wepresent a general method that solves most locally checkable labeling (LCL)problems exponentially faster in the low-space MPC model than in the LOCALmessage passing model. In particular, we show that all solvable LCL problems ontrees can be solved in $O(\log n)$ time (high-complexity regime) and that allLCL problems on trees with deterministic complexity $n^{o(1)}$ in the LOCALmodel can be solved in $O(\log \log n)$ time (mid-complexity regime). Weobserve that obtaining a greater speed-up than from $n^{o(1)}$ to $\Theta(\log\log n)$ is conditionally impossible, since the problem of 3-coloring trees,which is a LCL problem with LOCAL time complexity $n^{o(1)}$, has a conditionalMPC lower bound of $\Omega(\log \log n)$ [Linial, FOCS'87; Ghaffari, Kuhn andUitto, FOCS'19]. We emphasize that we solve LCL problems on constant-degreetrees, and that our algorithms are deterministic, component-stable, and work inthe low-space MPC model, where local memory is $O(n^\delta)$ for $\delta \in(0,1)$ and global memory is $O(m)$.  For the high-complexity regime, there are two key ingredients. One is a novel$O(\log n)$-time tree rooting algorithm, which may be of independent interest.The other is a novel pointer-chain technique and analysis that allows us tosolve any solvable LCL problem on trees in $O(\log n)$ time. For themid-complexity regime, we adapt the approach by Chang and Pettie [FOCS'17], whogave a canonical LOCAL algorithm for solving LCL problems on trees.

Towards a Complexity Classification of LCL Problems in Massively Parallel Computation