标题： 局部认证的复杂性景观 显示英文标题

标题： Complexity landscape for local certification

摘要： 近期一项引人注目的研究工作描绘了分布式图算法的复杂性图谱。对于许多情况，已经确定了哪些时间复杂性存在，哪些不存在（也就是说，没有局部问题能够具有那样的最优算法复杂性）。在本文中，我们开始研究分布式图算法的空间复杂性的图谱。更确切地说，我们关注局部认证设置，在这种设置中，证明者向节点分配证书以认证属性，并且空间复杂性通过证书的大小来衡量。对于匿名路径和环路，我们揭示了一个令人惊讶的图谱： - 在路径中存在复杂性从$O(1)$到$\Theta(\log \log n)$的差距。 这是在局部认证中首次建立的差距。 - 存在一个属性在路径中的复杂性为$\Theta(\log \log n)$，这是一个对于自然属性来说未知存在的复杂性等级。 - 在环路中存在复杂性从$O(1)$到$\Theta(\log n)$的差距，因此比路径中的差距大得多。 然后我们将路径的结果推广到树类。 即，我们证明了在树的复杂度$O(1)$和$\Theta(\log \log d)$之间存在差距，其中$d$是直径。 我们最后描述了一些完全没有差距的情况。 为了证明我们的结果，我们发展了一套新的工具包，基于自动机理论和算术的各种结果，这套工具包本身具有独立的研究价值。 显示英文摘要

摘要： An impressive recent line of work has charted the complexity landscape of distributed graph algorithms. For many settings, it has been determined which time complexities exist, and which do not (in the sense that no local problem could have an optimal algorithm with that complexity). In this paper, we initiate the study of the landscape for space complexity of distributed graph algorithms. More precisely, we focus on the local certification setting, where a prover assigns certificates to nodes to certify a property, and where the space complexity is measured by the size of the certificates. Already for anonymous paths and cycles, we unveil a surprising landscape: - There is a gap between complexity $O(1)$ and $\Theta(\log \log n)$ in paths. This is the first gap established in local certification. - There exists a property that has complexity $\Theta(\log \log n)$ in paths, a regime that was not known to exist for a natural property. - There is a gap between complexity $O(1)$ and $\Theta(\log n)$ in cycles, hence a gap that is exponentially larger than for paths. We then generalize our result for paths to the class of trees. Namely, we show that there is a gap between complexity $O(1)$ and $\Theta(\log \log d)$ in trees, where $d$ is the diameter. We finally describe some settings where there are no gaps at all. To prove our results we develop a new toolkit, based on various results of automata theory and arithmetic, which is of independent interest.