论文标题
树木及以后的分布式复杂性的景观
The Landscape of Distributed Complexities on Trees and Beyond
论文作者
论文摘要
我们研究恒定图表上本地可检查标签（LCL）问题的局部复杂性格局，重点是$ \ log^* n $的复杂性。 我们的贡献是三重的： 我们的主要贡献是，我们通过证明每个具有局部复杂性的LCL问题$ O（\ log^* n）$实际上具有复杂性$ O（1）$，从而完成了本地模型中LCL问题的复杂性格局的分类。 [cang，pettie，focs 2017] $ o（\ log \ log \ log^* n）$从$ o（\ log \ log \ log^* n）$（$ o（1）$）提高了此结果。 在相关的LCA和音量模型中[Alon，Rubinfeld，Vardi，Xie，Soda 2012，Rubinfeld，Tamir，Vardi，Vardi，Xie，2011年，Rosenbaum，Suomela，PODC 2020]，我们证明了从$ O（\ log^* n）$ o（$ o（1）$图形的$ o（log log^* n）$（1）$的$图形图。 同样，我们通过证明任何具有局部复杂性的LCL问题$ O（\ log^* n）$实际上具有复杂性$ O（1）$，从而完成了定向$ d $二维网格的局部复杂性格局的分类。这可以从先前的$ o（\ sqrt [d] {\ log^* n}）$的速度加快[Chang，Pettie，focs 2017]。
We study the local complexity landscape of locally checkable labeling (LCL) problems on constant-degree graphs with a focus on complexities below $\log^* n$. Our contribution is threefold: Our main contribution is that we complete the classification of the complexity landscape of LCL problems on trees in the LOCAL model, by proving that every LCL problem with local complexity $o(\log^* n)$ has actually complexity $O(1)$. This result improves upon the previous speedup result from $o(\log \log^* n)$ to $O(1)$ by [Chang, Pettie, FOCS 2017]. In the related LCA and Volume models [Alon, Rubinfeld, Vardi, Xie, SODA 2012, Rubinfeld, Tamir, Vardi, Xie, 2011, Rosenbaum, Suomela, PODC 2020], we prove the same speedup from $o(\log^* n)$ to $O(1)$ for all bounded degree graphs. Similarly, we complete the classification of the LOCAL complexity landscape of oriented $d$-dimensional grids by proving that any LCL problem with local complexity $o(\log^* n)$ has actually complexity $O(1)$. This improves upon the previous speed-up from $o(\sqrt[d]{\log^* n})$ by Suomela in [Chang, Pettie, FOCS 2017].
