Search papers, labs, and topics across Lattice.
This paper addresses the complexity gaps in locally checkable labeling (LCL) problems by demonstrating that these gaps arise from the constraints on graph degree rather than the local checkability of solutions. The authors establish that infinitely many LCL problems exhibit round complexities in the intervals $[\omega(1),o(\log\log^\star n)]$ and $[\omega(\log^\star n),o(\log n)]$ when analyzed in networks with unbounded maximum degrees. Utilizing deterministic algorithms under the port-numbering model, they derive upper bounds, while lower bounds are shown to apply to both randomized and quantum LOCAL models, even under various conditions regarding node identifiers and knowledge of network size.
Infinitely many locally checkable problems can achieve surprising round complexities in unbounded-degree graphs, challenging previous assumptions about complexity constraints.
We show that the complexity gaps in the round complexities of locally checkable labeling (LCL) problems are not due to the fact that solutions to LCL problems must be locally checkable, but solely to the fact that LCL problems are defined only for graphs of maximum degree upper bounded by some arbitrary yet constant value $\Delta$. Specifically, we show that there are infinitely many locally checkable problems (i.e., problems whose solutions can be checked locally) whose round complexities belongs to the two intervals $[\omega(1),o(\log\log^\star n)]$ and $[\omega(\log^\star n),o(\log n)]$ whenever these problems are considered in networks with unbounded maximum degrees. This extends the previous results by Schmid (arXiv, 2026), which hold for the polynomial regime only, and by Bousquet, Feuilloley, and Pierron (OPODIS, 2025), which hold for trees only. All our upper bounds are obtained using deterministic algorithms that can be run under the port-numbering model, which is a weak variant of LOCAL, without any a priori information on the number of nodes in the network. Instead, our lower bounds apply to randomized LOCAL, and quantum LOCAL, even if nodes have identifiers in $[1,n]$, and even if they know the exact number of nodes in the network. They even hold under randomized online LOCAL, a strong variant of the LOCAL model. Finally, our lower bounds hold even for trees. Our results are obtained using two main ingredients. The first one is the analysis of a new locally checkable problem called Increasing Degree, parameterized by a function $f:\mathbb{N}\to\mathbb{N}$. Different round complexities can be obtained by tuning the function $f$ accordingly. Our second tool is a general Translation Theorem that enables to transfer results from a given range of complexities to results for a range of lower complexities.
