Search papers, labs, and topics across Lattice.
This paper establishes that any locally checkable labeling problem (LCL) on trees solvable by an $n^{o(1)}$-dependent distribution can be addressed by an $O(\log n)$-round deterministic LOCAL algorithm. The authors employ a rake-and-compress decomposition of the input tree, facilitating local simulations of the bounded dependent distribution across the decomposed components. A significant corollary of this work is that all LCL problems on trees can be solved in $O(\log n)$ rounds deterministically or require $n^{\Omega(1)}$ rounds in a quantum-LOCAL setting, highlighting a stark contrast in complexity.
LCL problems on trees can be solved in logarithmic time, revealing a surprising efficiency gap between deterministic and quantum-LOCAL algorithms.
We show that, on trees, any locally checkable labeling problem (LCL) $\Pi$ 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^{\Omega(1)}$ rounds to solve by a quantum-LOCAL algorithm.
