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 Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Recent research revealed the existence of gaps in the complexity landscape oflocally checkable labeling (LCL) problems in the LOCAL model of distributedcomputing. For example, the deterministic round complexity of any LCL problemon bounded-degree graphs is either $O(\log^\ast n)$ or $\Omega(\log n)$ [Chang,Kopelowitz, and Pettie, FOCS 2016]. The complexity landscape of LCL problems isnow quite well-understood, but a few questions remain open.  For bounded-degree trees, there is an LCL problem with round complexity$\Theta(n^{1/k})$ for each positive integer $k$ [Chang and Pettie, FOCS 2017].It is conjectured that no LCL problem has round complexity $o(n^{1/(k-1)})$ and$\omega(n^{1/k})$ on bounded-degree trees. As of now, only the case of $k = 2$has been proved [Balliu et al., DISC 2018].  In this paper, we show that for LCL problems on bounded-degree trees, thereis indeed a gap between $\Theta(n^{1/(k-1)})$ and $\Theta(n^{1/k})$ for each $k\geq 2$. Our proof is constructive in the sense that it offers a sequentialalgorithm that decides which side of the gap a given LCL problem belongs to. Wealso show that it is EXPTIME-hard to distinguish between $\Theta(1)$-round and$\Theta(n)$-round LCL problems on bounded-degree trees. This improves upon aprevious PSPACE-hardness result [Balliu et al., PODC 2019].

The Complexity Landscape of Distributed Locally Checkable Problems on Trees