Superlogarithmic Gap Result for LCLs on Trees in Quantum-LOCAL
2026-08-17 • Computational Complexity
Computational ComplexityDistributed, Parallel, and Cluster Computing
AI summaryⓘ
The authors studied special labeling problems on trees, where solutions need to be checked locally. They showed that if a problem can be solved using certain complex random methods with weak dependencies, then it can also be solved by a straightforward step-by-step algorithm in about log(n) rounds. They achieved this by breaking down the tree into simpler parts and simulating the random methods locally. As a bonus, they found that any such problem on trees either has a fast deterministic solution or needs a long time even for quantum algorithms.
Locally Checkable Labeling (LCL)Trees (graph theory)Deterministic LOCAL algorithmRake-and-compress decompositionDependent distributionsQuantum LOCAL algorithmsRound complexityDistributed computingGraph decomposition
Authors
Francesco d'Amore, Henrik Lievonen
Abstract
We show that, on trees, any locally checkable labeling problem (LCL) $Π$ that can be solved by an $n^{o(1)}$-dependent distribution can also be solved by an $O(\log n)$-round deterministic LOCAL algorithm. The result is obtained through a rake-and-compress-style decomposition of the input tree, and local simulations of the bounded dependent distribution on the components of the decomposition. As a corollary to our result, any LCL problem on trees can either be solved by an $O(\log n)$ deterministic LOCAL algorithm, or requires $n^{Ω(1)}$ rounds to solve by a quantum-LOCAL algorithm.