Superlogarithmic Gap Result for LCLs on Trees in Quantum-LOCAL

Francesco d'Amore, Henrik Lievonen

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 deter…