论文标题
确定性分布式算法和δ规范树上的描述性组合学
Deterministic Distributed algorithms and Descriptive Combinatorics on Δ-regular trees
论文作者
论文摘要
我们从分布的局部算法和描述性组合学的角度研究了常规树上局部问题的复杂性类别。我们表明，令人惊讶的是，来自分布式计算的层次结构的某些确定性局部复杂性类别与描述性组合学中研究的一类问题相吻合。也就是说，我们表明，当且仅当它接受具有局部复杂性$ o（\ log^* n）$的本地算法时，局部问题就会接受一个连续的解决方案，而仅当它及时仅当它接受具有局部复杂性$ o（\ log n）$的局部算法时。
We study complexity classes of local problems on regular trees from the perspective of distributed local algorithms and descriptive combinatorics. We show that, surprisingly, some deterministic local complexity classes from the hierarchy of distributed computing exactly coincide with well studied classes of problems in descriptive combinatorics. Namely, we show that a local problem admits a continuous solution if and only if it admits a local algorithm with local complexity $O(\log^* n)$, and a Baire measurable solution if and only if it admits a local algorithm with local complexity $O(\log n)$.
