New LCL constructions fill LOCAL complexity gaps in unbounded-degree graphs

In distributed computing, the LOCAL model measures how many communication rounds nodes need to solve a problem on a network. For locally checkable labeling (LCL) problems — where a solution is valid if every node can verify its neighborhood — researchers had observed that certain round complexity ranges were impossible, creating 'gaps' between easy and hard problems. This paper by Filippo Casagrande, Pierre Fraigniaud, Benjamin Jauregui, and Mikaël Rabie shows that these gaps are not inherent to local checkability itself, but instead stem from the standard assumption that the maximum graph degree Δ is bounded by a constant.

The authors construct infinitely many LCL problems that achieve round complexities in the two forbidden intervals: between ω(1) and o(log log* n), and between ω(log* n) and o(log n). They do this using a new problem called 'Increasing Degree', parameterized by a function f, which can be tuned to land in specific complexity ranges. A general 'Translation Theorem' then transfers these results across different complexity regimes. All upper bounds are achieved by deterministic algorithms running under the port-numbering model, which is weaker than LOCAL and requires no knowledge of n. The lower bounds are stronger: they hold even for randomized LOCAL, quantum LOCAL, and online LOCAL — and they apply to trees as well. This significantly extends prior work by Schmid (2026) and by Bousquet, Feuilloley, and Pierron (2025), which only covered polynomial regimes or tree-only cases.