Summary: The landscape of the distributed time complexity is nowadays well-understood for subpolynomial complexities. When we look at deterministic algorithms in the \(\mathsf{LOCAL}\) model and locally checkable problems (\(\mathsf{LCL}\)s) in bounded-degree graphs, the following picture emerges:

–

There are lots of problems with time complexities of \(\varTheta (\log^* n)\) or \(\varTheta (\log n)\).

–

It is not possible to have a problem with complexity between \(\omega (\log^* n)\) and \(o(\log n)\).

–

In general graphs, we can construct \(\mathsf{LCL}\) problems with infinitely many complexities between \(\omega (\log n)\) and \(n^{o(1)} \).

–

In trees, problems with such complexities do not exist.

However, the high end of the complexity spectrum was left open by prior work. In general graphs there are \(\mathsf{LCL}\) problems with complexities of the form \(\varTheta (n^\alpha )\) for any rational \(0 < \alpha \le 1/2\), while for trees only complexities of the form \(\varTheta (n^{1/k})\) are known. No \(\mathsf{LCL}\) problem with complexity between \(\omega (\sqrt{n})\) and \(o(n)\) is known, and neither are there results that would show that such problems do not exist. We show that:

–

In general graphs, we can construct \(\mathsf{LCL}\) problems with infinitely many complexities between \(\omega (\sqrt{n})\) and \(o(n)\).

–

In trees, problems with such complexities do not exist.

Put otherwise, we show that any \(\mathsf{LCL}\) with a complexity \(o(n)\) can be solved in time \(O(\sqrt{n})\) in trees, while the same is not true in general graphs.