pith. sign in

arxiv: 2606.10693 · v1 · pith:IKGBTURPnew · submitted 2026-06-09 · 💻 cs.DC · cs.CC· cs.FL

Generalizing LCL Complexity Gaps to Unbounded Degree via Monadic Second-Order Properties

Chiara Piombi This is my paper

Pith reviewed 2026-06-27 11:57 UTC · model grok-4.3

classification 💻 cs.DC cs.CCcs.FL
keywords LCL problemsLOCAL modelcomplexity gapsunbounded degreerooted treesPMSO formulasLPMSO problemsdistributed algorithms
0
0 comments X

The pith

The ω(log n) - n^{o(1)} and ω(n^{1/(k+1)}) - o(n^{1/k}) complexity gaps for LCL problems extend to LPMSO problems on unbounded degree rooted trees, along with their decidability.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Previous work established complexity gaps for LCL problems on bounded-degree trees in the LOCAL model. This paper generalizes LCL to LPMSO problems, which use Presburger monadic second-order formulas to describe solutions on graphs of arbitrary degree while remaining locally verifiable in constant time. It proves that the same gaps—no problems with complexity between ω(log n) and n^{o(1)}, and between ω(n^{1/(k+1)}) and o(n^{1/k}) for each k—hold for LPMSO on unbounded-degree rooted trees. The decidability of which side of the gap a given problem lies on also carries over. This allows classification of a wider range of distributed problems that involve properties like degree counts or arithmetic on labels.

Core claim

On unbounded degree rooted trees, the aforementioned ω(log n) - n^{o(1)} and ω(n^{1/(k+1)}) - o(n^{1/k}) complexity gaps (and their decidability) extend to the class of LPMSO problems.

What carries the argument

LPMSO problems, defined as problems whose correct solutions are finitely described by a PMSO formula and locally verifiable by a constant-time LOCAL algorithm, which generalizes LCL to unbounded degrees.

If this is right

  • The same complexity classification applies to problems on graphs with arbitrary degrees.
  • Decidability of which side of each gap a problem occupies carries over to LPMSO.
  • No LPMSO problem can achieve complexities in the forbidden ranges on unbounded degree rooted trees.
  • Many important problems studied in the LOCAL model can now be defined and classified on unbounded degree graphs.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The gaps appear robust to removal of the degree bound when solutions are captured by monadic second-order properties with Presburger arithmetic.
  • The same transfer technique might classify problems on other unbounded-degree graph families if local checkability can be preserved.
  • LPMSO problems that count or compare degrees could serve as test cases to probe the exact boundaries of the gaps.
  • Decidability results may extend to deciding complexity classes for related problems in other distributed models.

Load-bearing premise

The local verifiability condition for LPMSO problems permits direct transfer of proof techniques from bounded-degree LCL without introducing new gaps or decidability obstacles.

What would settle it

An explicit LPMSO problem on unbounded-degree rooted trees whose LOCAL complexity falls strictly between ω(log n) and n^{o(1)} would falsify the extension of the gaps.

Figures

Figures reproduced from arXiv: 2606.10693 by Chiara Piombi.

Figure 1
Figure 1. Figure 1: The complexity landscape of LCLs on general graphs. the types of graphs the problem is defined on: the complexity landscape of LCL problems is fully understood for many graph classes, such as paths [Bal+19b], undirected trees [Cha20], rooted trees [Bal+21], and grids [Bra+17]. We focus especially on undirected and rooted trees; they have very similar complexity landscapes, as a problem on rooted trees can … view at source ↗
Figure 2
Figure 2. Figure 2: The complexity landscape of LCLs on undirected trees. 1 log∗n log n n n 1/k [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: The complexity landscape of LCLs on rooted trees; note that the randomized and deterministic landscapes are the same. 3 [PITH_FULL_IMAGE:figures/full_fig_p003_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Replacing T1 by T2 in the context C[x]. Definition 3.11. Given a graph language G, we define an equivalence relation ≡G as follows: T1 ≡G T2 if and only if for every context C we have C[T1] ∈ G if and only if C[T2] ∈ G. In other words, T1 ≡G T2 if replacing T1 by T2 in a tree does not affect membership in G. Given a deterministic, complete rational multiset tree automaton A, for every rooted tree T we have… view at source ↗
Figure 5
Figure 5. Figure 5: Using ForgetChildren and the feasible function to label bipolar trees. Lemma 3.29. Let ΠA be the problem associated to the rational multiset tree automaton A = (Σ, Q, δ, F). Let Alab = (Σ×(Q⊎{∗}), 2 Q, δlab, Flab) be the partially labeled type automaton of A. Then for any Σ-labeled and partially Q-labeled rooted tree G with root r the following statements are equivalent: (1) the type assigned by Alab to r … view at source ↗
read the original abstract

The last decade of research on the LOCAL model has seen tremendous progress in understanding locally checkable labeling (LCL) problems, culminating in an almost complete classification of the possible complexities LCL problems can exhibit. In particular, on undirected trees, Chang and Pettie showed that there is no LCL problem with complexity between $\omega(\log n)$ and $n^{o(1)}$ and Chang showed that, for every positive integer $k$, there is no LCL problem with complexity between $\omega(n^{1/(k+1)})$ and $o(n^{1/k})$; additionally, which side of each gap a problem is found on is decidable. While the class of LCL problems - which, roughly speaking, consists of problems for which the correctness of a solution can be described by a finite set of allowed node configurations, which in turn can be locally verified by a constant-time algorithm - includes many important problems, it has one major restriction: problems can be defined only on bounded degree graphs, which consequently restricts all the classification and gap results mentioned above. In this work, we propose a generalization of LCL problems to unbounded degree using Presburger monadic second-order (PMSO) formulas; more specifically, we consider what we call Local PMSO (LPMSO) problems, i.e., problems whose correct solutions are both finitely described by a PMSO formula and locally verifiable by a LOCAL algorithm in constant time - this class contains many of the important problems studied in the LOCAL model but defines them on unbounded degree graphs. As our main result we prove that, on unbounded degree rooted trees, the aforementioned $\omega(\log n)$ - $n^{o(1)}$ and $\omega(n^{1/(k+1)})$ - $o(n^{1/k})$ complexity gaps (and their decidability) extend to the class of LPMSO problems.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The paper introduces Local Presburger Monadic Second-Order (LPMSO) problems as a generalization of LCL problems to unbounded-degree graphs. LPMSO problems are defined via PMSO formulas whose solutions are finitely described and locally verifiable in constant time by a LOCAL algorithm. The main result states that on unbounded-degree rooted trees, the ω(log n)–n^{o(1)} and ω(n^{1/(k+1)})–o(n^{1/k}) complexity gaps (and the decidability of which side of each gap a problem occupies) extend from LCL to the LPMSO class.

Significance. If the result holds, it removes the bounded-degree restriction that limited prior LCL gap theorems, allowing the classification to apply to a larger family of problems that arise naturally on general graphs. The decidability component would remain a practical tool for classifying new problems. The work directly addresses a stated limitation of the Chang–Pettie and Chang results.

major comments (1)
  1. [Abstract] Abstract (main theorem statement): the claim that the gaps and decidability extend rests on the assertion that constant-time local verifiability permits direct transfer of the finite-configuration automata techniques from bounded-degree LCL proofs. However, on unbounded-degree rooted trees a radius-1 view already contains arbitrarily many children, yielding infinitely many local configurations. The manuscript must therefore supply either (a) an effective reduction from any LPMSO instance to a finite-configuration LCL instance or (b) a self-contained argument that the gap and decidability proofs survive the infinite-configuration setting. Neither step is visible in the abstract, and this is load-bearing for the central claim.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful review and for identifying the load-bearing aspect of the central claim. We address the major comment below.

read point-by-point responses

  1. Referee: [Abstract] Abstract (main theorem statement): the claim that the gaps and decidability extend rests on the assertion that constant-time local verifiability permits direct transfer of the finite-configuration automata techniques from bounded-degree LCL proofs. However, on unbounded-degree rooted trees a radius-1 view already contains arbitrarily many children, yielding infinitely many local configurations. The manuscript must therefore supply either (a) an effective reduction from any LPMSO instance to a finite-configuration LCL instance or (b) a self-contained argument that the gap and decidability proofs survive the infinite-configuration setting. Neither step is visible in the abstract, and this is load-bearing for the central claim.

    Authors: The full manuscript supplies option (b). LPMSO problems are defined so that solutions are finitely described by a PMSO formula; this finite description (via Presburger arithmetic on node counts) replaces the finite set of configurations used in bounded-degree LCL proofs. Sections 3–5 contain a self-contained adaptation: we lift the automata constructions by working directly with the decidable theory of PMSO rather than enumerating configurations, preserving both the gap theorems and the decidability of which side of each gap a problem occupies. We agree the abstract does not indicate this adaptation and will revise it to state that the PMSO finite-description property enables the extension. This is a clarification rather than a change to the technical argument. revision: partial

Circularity Check

0 steps flagged

No circularity; extension builds on external prior results without reduction to inputs

full rationale

The paper extends gap theorems from Chang-Pettie and Chang (external citations) to LPMSO problems via the definition of local PMSO verifiability on unbounded-degree trees. No self-definitional steps, fitted parameters renamed as predictions, or load-bearing self-citations appear. The derivation chain relies on the stated local checkability to transfer techniques, but remains independent of its own outputs and is self-contained against the cited external benchmarks. No quoted reduction of the main claim to its inputs by construction is present.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The central claim rests on the new definition of LPMSO problems; no free parameters are mentioned.

axioms (1)
  • domain assumption Problems whose solutions are finitely described by a PMSO formula remain locally verifiable in constant time by a LOCAL algorithm
    This is the key property used to define the LPMSO class in the abstract.
invented entities (1)
  • LPMSO problems no independent evidence
    purpose: Generalize LCL problems to unbounded-degree graphs while preserving local checkability
    New class introduced by the paper; no independent evidence outside the definition itself.

pith-pipeline@v0.9.1-grok · 5882 in / 1227 out tokens · 20690 ms · 2026-06-27T11:57:10.745334+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

19 extracted references · 17 canonical work pages · 1 internal anchor

  1. [1]

    New classes of distributed time complexity

    [Bal+18] Alkida Balliu et al. “New classes of distributed time complexity”. In:Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29,

    2018

  2. [2]

    Lower Bounds for Maximal Matchings and Maximal Indepen- dent Sets

    Ed. by Ilias Diakonikolas, David Kempe,andMonikaHenzinger.ACM,2018,pp.1307–1318.doi:10.1145/3188745. 3188860.url:https://doi.org/10.1145/3188745.3188860. [Bal+19a] Alkida Balliu et al. “Lower Bounds for Maximal Matchings and Maximal Indepen- dent Sets”. In:60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, ...

    work page doi:10.1145/3188745 2018

  3. [3]

    The Distributed Complexity of Locally Checkable Problems on Paths is Decidable

    Ed. by David Zuck- erman. IEEE Computer Society, 2019, pp. 481–497.doi:10 . 1109 / FOCS . 2019 . 00037.url:https://doi.org/10.1109/FOCS.2019.00037. [Bal+19b] Alkida Balliu et al. “The Distributed Complexity of Locally Checkable Problems on Paths is Decidable”. In:Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toro...

    work page doi:10.1109/focs.2019.00037 2019

  4. [4]

    Classification of Distributed Binary Labeling Problems

    Ed. by Peter Robinson and Faith Ellen. ACM, 2019, pp. 262–271.doi: 10.1145/3293611.3331606.url:https://doi.org/10.1145/3293611.3331606. [Bal+20] Alkida Balliu et al. “Classification of Distributed Binary Labeling Problems”. In: 34th International Symposium on Distributed Computing, DISC 2020, Virtual Con- ference, October 12-16,

    work page doi:10.1145/3293611.3331606.url:https://doi.org/10.1145/3293611.3331606 2019

  5. [5]

    Locally Checkable Problems in Rooted Trees

    Ed. by Hagit Attiya. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, 17:1–17:17.doi:10 . 4230 / LIPICS . DISC . 2020.17.url:https://doi.org/10.4230/LIPIcs.DISC.2020.17. [Bal+21] Alkida Balliu et al. “Locally Checkable Problems in Rooted Trees”. In:PODC ’21: ACM Symposium on Principles of Distributed Computing, Virtual Event, Italy, July 26-30,

    work page doi:10.4230/lipics.disc.2020.17 2020

  6. [6]

    Sinkless Orientation Made Simple

    Ed. by Avery Miller, Keren Censor-Hillel, and Janne H. Korhonen. ACM, 2021, pp. 263–272.doi:10.1145/3465084.3467934.url:https://doi. org/10.1145/3465084.3467934. [Bal+23] Alkida Balliu et al. “Sinkless Orientation Made Simple”. In:Symposium on Simplic- ity in Algorithms (SOSA). Society for Industrial and Applied Mathematics, 2023, 175–191.isbn: 9781611977...

    work page doi:10.1145/3465084.3467934.url:https://doi 2021

  7. [7]

    LCL Problems on Grids

    Ed. by Rida A. Bazzi and Boaz Patt- Shamir. ACM, 2008, pp. 25–34.doi:10 . 1145 / 1400751 . 1400757.url:https : //doi.org/10.1145/1400751.1400757. 34 [Bra+17] Sebastian Brandt et al. “LCL Problems on Grids”. In:Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC 2017, Washington, DC, USA, July 25-27,

    work page doi:10.1145/1400751.1400757 2008

  8. [8]

    Automata and Logics for Unranked and Un- ordered Trees

    Ed. by Elad Michael Schiller and Alexander A. Schwarz- mann. ACM, 2017, pp. 101–110.doi:10 . 1145 / 3087801 . 3087833.url:https : //doi.org/10.1145/3087801.3087833. [BT05] Iovka Boneva and Jean-Marc Talbot. “Automata and Logics for Unranked and Un- ordered Trees”. In:Term Rewriting and Applications, 16th International Conference, RTA 2005, Nara, Japan, Ap...

    work page doi:10.1145/3087801.3087833 2017

  9. [9]

    The Complexity Landscape of Distributed Locally Checkable Prob- lems on Trees

    Encyclopedia of mathematics and its applications. Cambridge University Press, 2012.isbn: 978-0-521-89833-1.url: http://www.cambridge.org/fr/knowledge/isbn/item5758776/?site\_locale= fr\_FR. [Cha20] Yi-Jun Chang. “The Complexity Landscape of Distributed Locally Checkable Prob- lems on Trees”. In:34th International Symposium on Distributed Computing, DISC 2...

    2012

  10. [10]

    Hendrych, M

    Ed. by Hagit Attiya. LIPIcs. Schloss Dagstuhl-Leibniz-ZentrumfürInformatik,2020,18:1–18:17.doi:10.4230/LIPICS. DISC.2020.18.url:https://doi.org/10.4230/LIPIcs.DISC.2020.18. [CMM00] Erzsébet Csuhaj-Varjú, Carlos Martín-Vide, and Victor Mitrana. “Multiset Au- tomata”. In:Multiset Processing, Mathematical, Computer Science, and Molecular Computing Points of ...

    work page doi:10.4230/lipics 2020

  11. [11]

    A Time Hierarchy Theorem for the LOCAL Model

    Elsevier, 2002, pp. 40–54.doi:10.1016/S1571-0661(04)80532-2.url: https://doi.org/10.1016/S1571-0661(04)80532-2. [Com+08] Hubert Comon et al.Tree Automata Techniques and Applications. HAL, 2008, p. 262.url:https://inria.hal.science/hal-03367725. [CP17] Yi-Jun Chang and Seth Pettie. “A Time Hierarchy Theorem for the LOCAL Model”. In:58th IEEE Annual Symposi...

    work page doi:10.1016/s1571-0661(04)80532-2.url: 2002

  12. [12]

    Rationalsetsincommutativemonoids

    Ed. by Chris Umans. IEEE Com- puter Society, 2017, pp. 156–167.doi:10 . 1109 / FOCS . 2017 . 23.url:https : //doi.org/10.1109/FOCS.2017.23. [ES69] SamuelEilenbergandM.PSchützenberger.“Rationalsetsincommutativemonoids”. In:Journal of Algebra13.2 (Oct. 1969), 173–191.issn: 0021-8693.doi:10.1016/ 0021 - 8693(69 ) 90070 - 2.url:http : / / dx . doi . org / 10 ...

    work page doi:10.1109/focs.2017.23 2017

  13. [13]

    On the Impact of Identifiers on Local Decision

    Ed. by Alessia Milani and Philipp Woelfel. ACM, 2022, pp. 131–140.doi:10.1145/3519270.3538416.url:https://doi.org/10.1145/ 3519270.3538416. 35 [FHK12] Pierre Fraigniaud, Magnús M. Halldórsson, and Amos Korman. “On the Impact of Identifiers on Local Decision”. In:Principles of Distributed Systems, 16th Interna- tional Conference, OPODIS 2012, Rome, Italy, ...

    work page doi:10.1145/3519270.3538416.url:https://doi.org/10.1145/ 2022

  14. [14]

    What can be decided locally without identifiers?

    Proceedings. Ed. by Roberto Baldoni, Paola Flocchini, and Binoy Ravindran. Lecture Notes in Computer Science. Springer, 2012, pp. 224–238.doi:10.1007/978-3-642-35476- 2\_16.url:https://doi.org/10.1007/978-3-642-35476-2\_16. [Fra+13] Pierre Fraigniaud et al. “What can be decided locally without identifiers?” In: ACM Symposium on Principles of Distributed C...

    work page doi:10.1007/978-3-642-35476- 2012

  15. [15]

    Semigroups, Presburger formulas, and lan- guages

    Ed. by Panagiota Fatourou and Gadi Taubenfeld. ACM, 2013, pp. 157–165.doi:10.1145/2484239.2484264.url:https://doi. org/10.1145/2484239.2484264. [GS66] Seymour Ginsburg and Edwin Spanier. “Semigroups, Presburger formulas, and lan- guages”. In:Pacific Journal of Mathematics16.2 (Feb. 1966), 285–296.issn: 0030- 8730.doi:10.2140/pjm.1966.16.285.url:http://dx....

    work page doi:10.1145/2484239.2484264.url:https://doi 2013

  16. [16]

    Distributive Graph Algorithms-Global Solutions from Local Data

    Ed. by Chris- tian Scheideler. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, 26:1–26:24.doi:10.4230/LIPICS.DISC.2022.26.url:https://doi.org/10. 4230/LIPIcs.DISC.2022.26. [Jau+18] Benjamin Jauregui et al.Distributed Treewidth Computation and Courcelle’s The- orem in the CONGEST Model. 2018.doi:10 . 48550 / ARXIV . 1805 . 10708.url: https...

    work page doi:10.4230/lipics.disc.2022.26.url:https://doi.org/10 2022

  17. [17]

    Locality in Distributed Graph Algorithms

    IEEE Computer Society, 1987, pp. 331–335. doi:10.1109/SFCS.1987.20.url:https://doi.org/10.1109/SFCS.1987.20. [Lin92] Nathan Linial. “Locality in Distributed Graph Algorithms”. In:SIAM J. Comput. 21.1 (1992), pp. 193–201.doi:10 . 1137 / 0221015.url:https : / / doi . org / 10 . 1137/0221015. [NS93] Moni Naor and Larry J. Stockmeyer. “What can be computed lo...

    work page doi:10.1109/sfcs.1987.20.url:https://doi.org/10.1109/sfcs.1987.20 1987

  18. [18]

    LCLs Beyond Bounded Degrees

    arXiv:2602.02340 [cs.DC]. url:https://arxiv.org/abs/2602.02340. [SSM03] HelmutSeidl,ThomasSchwentick,andAncaMuscholl.“Numericaldocumentqueries”. In:Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. SIGMOD/PODS03. ACM, 2003, 155–166.doi: 10.1145/773153.773169.url:http://dx.doi.org/10.1145/773153.773169. ...

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1145/773153.773169.url:http://dx.doi.org/10.1145/773153.773169 2003

  19. [19]

    does there exist aΣ-labeleddirectedtreeT d such that c(Td) =T?

    Ed. by Susanne Albers. LIPIcs. Schloss Dagstuhl - Leibniz- Zentrum für Informatik, 2020, 2:1–2:1.doi:10.4230/LIPICS.SWAT.2020.2.url: https://doi.org/10.4230/LIPIcs.SWAT.2020.2. A Converting between problem types Throughout the proof of Theorem 1.2, we treatΠA,∆ alternatively as a problem on bounded degreerootedtrees (with or without inputs) and as a probl...

    work page doi:10.4230/lipics.swat.2020.2.url: 2020