Pith. sign in

REVIEW 6 minor 24 references

New Complexity Classes in Locally Checkable Labeling for Local Computation Algorithms

T0 review · 0 major / 6 minor · reviewed 2026-07-13 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Stacking known LCL gadgets produces every polylog and every rational polynomial probe complexity for local computation algorithms.

desk verdict Solid stacking construction that fills the open polylog and rational-polynomial slots for VOLUME/LCA LCLs, answering Rosenbaum–Suomela directly. read the letter →

arxiv 2607.09626 v1 pith:Q7M4FEIQ submitted 2026-07-10 cs.DC cs.DS

Sijin Peng This is my paper · ORCID
classification cs.DCcs.DS
keywords localcomputationalgorithmsVOLUMEmodellocallycheckablelabelingprobecomplexitylandscapestackingconstructions
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

Local computation algorithms must answer queries about a consistent global solution to a massive graph problem while probing only a tiny portion of the input. Restricting attention to locally checkable labeling problems—constant-degree constraint-satisfaction problems whose solutions can be verified by looking at constant-radius neighborhoods—lets one ask a clean complexity-classification question: which probe-complexity functions actually arise? The paper answers that question for two natural regimes. By recursively stacking copies of two base constructions already known to require Θ(log n) and roughly n^{1/k} probes, it produces new LCLs whose randomized probe complexity is exactly Θ(log^k n) for every positive integer k and roughly n^x for every rational x between 0 and 1. The same bounds hold both for ordinary LCAs and for the more restricted VOLUME model, and they hold already on trees. The constructions therefore fill previously empty intervals of the complexity landscape and show that probe complexity can be far denser than the round-complexity landscape of the classical LOCAL model on the same problems.

What carries the argument

Stacking of base VOLUME gadgets (path-to-leaf and hierarchical two-coloring instances): each vertex of a higher-level instance is given a “twisted” input bit that is the XOR of a local bit and the root-output bit of a fresh lower-level copy; forcing the algorithm to solve all (or one carefully chosen) of those copies multiplies the probe cost and produces the desired exponents.

What would settle it

Exhibit either a randomized LCA that solves one of the stacked problems with o(log^k n) (respectively o(n^x / polylog n)) probes on the hard tree family, or a proof that every legal solution on that family can make the root bit depend on the unprobed input bits once intermediate labels are chosen adaptively.

Watch

Extended reading notes

Core claim

There exist LCL problems whose randomized probe complexities, in both the LCA and VOLUME models, are Θ(log^k n) for every positive integer k and ˜Θ(n^x) for every rational x in (0,1], already when the input is restricted to bounded-degree trees.

Load-bearing premise

The hard distributions are built so that every legal global solution must output one fixed bit at a designated root, no matter how the algorithm chooses intermediate direction or color labels.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 6 minor

Summary. The paper constructs new LCL complexity classes for randomized local computation algorithms (LCAs) and the VOLUME model. Using a stacking technique on base constructions of Rosenbaum–Suomela (LeafColoring / path-to-leaf and Hierarchical-THC), it proves that for every integer k≥1 there is an LCL with probe complexity Θ(log^k n) (Theorem 1, via Π^k_PTL), and for every rational x∈(0,1] there is an LCL with probe complexity ˜Θ(n^x) (Theorem 2, via Π^T_HC parameterized by the value of a good ordered binary tree T). Both upper and lower bounds hold for VOLUME and LCA, and on both bounded-degree graphs and trees. Upper bounds are explicit Las-Vegas algorithms (random walks, binary lifting, recursive “strong” algorithms) converted to Monte Carlo; lower bounds use hard distributions that force a fixed root output bit independent of direction/color choices, combined with Yao’s principle and inductive bijections that preserve any o(target-complexity) set of input bits.

Significance. The work answers two explicit open questions of Rosenbaum–Suomela on the density of randomized VOLUME complexities in the polylogarithmic and polynomial regimes, and simultaneously transfers the landscape to the LCA model and to trees. The stacking method is technically distinct from the Turing-machine encodings used for dense LOCAL complexities, and yields a clean, combinatorial explanation of how probe complexity can be finer-grained than distance complexity on trees. Explicit algorithms, matching hard distributions, and inductive arguments that close the adaptive-labeling loophole are genuine strengths; the results are therefore a solid, self-contained contribution to the complexity classification of LCLs under probe-based models.

minor comments (6)
  1. Definition 40 (strong algorithm) is the technical heart of the polynomial upper bound; a short informal paragraph immediately before it, summarizing the roles of N1 (ideal size), N2 (maximum size) and the two probe bounds (12)–(13), would make the subsequent induction far easier to follow.
  2. In §4.2–4.3 and §5.3–5.5 the inductive arguments are long and were partly AI-assisted. Adding a one-sentence “proof roadmap” at the start of each major lemma (especially Lemmas 25, 47, 52 and 56) would improve human readability without changing the mathematics.
  3. Figure 1 and Figure 2 are helpful, but the caption of Figure 2 should explicitly state that the solid blue segment covers every rational exponent, not merely a dense set of reals.
  4. Notation for ports (P, LC, RC, NC / DC) is overloaded between the multi-level binary-tree labeling and the T-labeling; a brief table or a consistent subscript convention would reduce cognitive load.
  5. Remark 8 (Las Vegas → Monte Carlo) is standard but should cite the precise success-probability budget used later (1−1/n or 1−n*/n^{2}) so that the conversion is fully mechanical.
  6. Section 6.2 correctly leaves open the polynomial separation of LCA versus VOLUME; a one-sentence pointer to the connectivity-reduction of Göös et al. already cited as [30] would make the remaining randomness question sharper.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: complexities arise from explicit combinatorial stacking of external base LCLs with self-contained inductive proofs.

full rationale

The paper’s central claims (Theorems 1–2) are existence results obtained by constructing new LCLs Π^k_PTL and Π^T_HC. Base cases (LeafColoring / Hierarchical-THC of Rosenbaum–Suomela 2020) are external published constructions, not self-citations by the present author. Stacking, multi-level binary-tree / T-labelings, xor-twisting of input bits, and the hard distributions of Lemmas 22 and 56 are defined and analyzed inside the paper; the inductive bijections (Lemma 25, induction on |T| in Lemma 56) force every legal solution to output a fixed root bit b_I independent of adaptive direction/color choices, so the Yao lower bounds do not reduce to their own inputs by construction. Upper bounds are explicit Las-Vegas algorithms (SolvePTL^k, the strong-algorithm induction for SolveHC_T) whose probe recurrences are solved directly. There are no fitted parameters, no uniqueness theorems imported from the same authors, and no renaming of known empirical patterns. The derivation chain is therefore self-contained combinatorial argument, not circular.

Assumptions & free parameters 0 free parameters · 3 assumptions · 2 invented entities

The paper works entirely inside standard models of distributed and local computation. No free parameters are fitted; the only background axioms are the definitions of LCL, LCA and VOLUME together with the existence of the two base constructions of Rosenbaum–Suomela that are stacked.

assumptions (3)
  • standard math Standard definitions of randomized LCA and VOLUME probe complexity (Definitions 5–6) and of LCL problems (Definition 3).
    Taken as given from the literature; used throughout.
  • domain assumption Existence of the LeafColoring / Hierarchical-THC LCLs of VOLUME complexity Θ(log n) and ˜Θ(n^{1/k}) (Rosenbaum–Suomela 2020).
    Base cases that are stacked; cited and reviewed in Section 2.
  • standard math Yao’s minimax principle for converting randomized lower bounds into deterministic distributional lower bounds.
    Used in the proofs of Lemmas 16 and 37.
invented entities (2)
  • Π^k_PTL (multi-level path-to-leaf LCL)
    purpose: Realizes Θ(log^k n) probe complexity by recursive attachment of binary-tree instances.
    Defined in Definition 13; the stacking depth k is a free design choice of the construction, not an empirical fit.
  • Π^T_HC (hierarchical coloring LCL parameterized by a good ordered binary tree T)
    purpose: Realizes ˜Θ(n^{val(T)}) probe complexity for every rational val(T)∈(0,1].
    Defined in Definition 33; the value function on ordered binary trees is introduced solely to generate all rationals.

how reviews work

0 comments
Cite this review

Pith. "Pith review of New Complexity Classes in Locally Checkable Labeling for Local Computation Algorithms." pith.science (2026). https://pith.science/paper/Q7M4FEIQ

@misc{pith2026260709626,
  author       = {Pith},
  title        = {Pith review of: New Complexity Classes in Locally Checkable Labeling for Local Computation Algorithms},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/Q7M4FEIQ}},
  note         = {Machine review of arXiv:2607.09626}
}
abstract

Local Computation Algorithms (LCAs), introduced by Rubinfeld, Tamir, Vardi, and Xie (2011), are a special type of sublinear algorithms that, given probing access to a possibly massive input, are required to provide query access to a consistent solution, without maintaining a state between different queries. In this paper, we try to understand LCA through the lens of complexity classifications, described by the following question: Given a target complexity function $f(n)$, is there a problem whose local computation complexity is $f(n)$, up to polylogarithmic factors? We restrict our focus to Locally Checkable Labeling (LCL) problems, which can be seen as constant-degree constraint satisfaction problems. Possible complexity classes of this problem family have been extensively studied in various distributed computation models, including the $\mathrm{VOLUME}$ model proposed by Rosenbaum and Suomela (2020), which is an invariant of local computation algorithms with additional locality requirements. In this paper, we provide new LCL complexity constructions in the $\mathrm{VOLUME}$ model, and generalize the results to LCAs. Specifically, we show that there are LCLs whose probe complexities in the $\mathrm{VOLUME}$ and LCA models are $\Theta(\log^k n)$ and $\tilde \Theta(n^{p/q})$ for any positive integer $k \ge 1$ and rational $p/q \in (0,1]$. Our approach, completely different from the approach to a similar result in the distributed $\mathrm{LOCAL}$ model by Balliu et al. (2018), is to stack instances of complexity $\Theta(\log n)$ and $\tilde \Theta(n^{1/k})$ in the $\mathrm{VOLUME}$ model constructed by Rosenbaum and Suomela (2020).

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

24 extracted references · 15 linked inside Pith

  1. [1]

    Locality in online, dynamic, sequential, and distributed graph algorithms.arXiv preprint arXiv:2109.06593,

    1 Amirreza Akbari, Navid Eslami, Henrik Lievonen, Darya Melnyk, Joona Särkijärvi, and Jukka Suomela. Locality in online, dynamic, sequential, and distributed graph algorithms.arXiv preprint arXiv:2109.06593,

    arXiv

  2. [2]

    The distributed complexity of locally checkable problems on paths is decidable

    4 Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, Mikaël Rabie, and Jukka Suomela. The distributed complexity of locally checkable problems on paths is decidable. InProceedings of the 2019 ACM Symposium on Principles of Distributed Computing, pages 262–271,

    2019

  3. [3]

    Efficient classification of locally checkable problems in regular trees.arXiv preprint arXiv:2202.08544,

    5 Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, Jan Studen` y, and Jukka Suomela. Efficient classification of locally checkable problems in regular trees.arXiv preprint arXiv:2202.08544,

    arXiv

  4. [4]

    The distributed complexity landscape on trees depends on the knowledge about the network size.arXiv preprint arXiv:2605.12787,

    6 Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti, Timothé Picavet, and Gustav Schmid. The distributed complexity landscape on trees depends on the knowledge about the network size.arXiv preprint arXiv:2605.12787,

    arXiv

  5. [5]

    Locally checkable problems in rooted trees

    7 Alkida Balliu, Sebastian Brandt, Dennis Olivetti, Jan Studen` y, Jukka Suomela, and Aleksandr Tereshchenko. Locally checkable problems in rooted trees. InProceedings of the 2021 ACM Symposium on Principles of Distributed Computing, pages 263–272,

    2021

  6. [6]

    Almost global problems in the local model.arXiv preprint arXiv:1805.04776,

    8 Alkida Balliu, Sebastian Brandt, Dennis Olivetti, and Jukka Suomela. Almost global problems in the local model.arXiv preprint arXiv:1805.04776,

    arXiv

  7. [7]

    Distributedquantumadvantage in locally checkable labeling problems

    10 Alkida Balliu, Filippo Casagrande, Francesco d’Amore, Massimo Equi, Barbara Keller, Henrik Lievonen, DennisOlivetti, GustavSchmid, andJukkaSuomela. Distributedquantumadvantage in locally checkable labeling problems. InProceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1268–1308. SIAM,

    2026

  8. [8]

    Locally checkable labelings with small messages.arXiv preprint arXiv:2105.05574,

    11 Alkida Balliu, Keren Censor-Hillel, Yannic Maus, Dennis Olivetti, and Jukka Suomela. Locally checkable labelings with small messages.arXiv preprint arXiv:2105.05574,

    arXiv

Show all 24 references
  1. [9]

    Shared randomness helps with local distributed problems

    12 Alkida Balliu, Mohsen Ghaffari, Fabian Kuhn, Augusto Modanese, Dennis Olivetti, Mikaël Rabie, Jukka Suomela, Jara Uitto, et al. Shared randomness helps with local distributed problems. InProceedings of the 52nd International Colloquium on Automata, Languages, and Programmin...

    2025

  2. [10]

    Separating complexity classes of lcl problems on grids.arXiv preprint arXiv:2501.17445,

    16 Katalin Berlow, Anton Bernshteyn, Clark Lyons, and Felix Weilacher. Separating complexity classes of lcl problems on grids.arXiv preprint arXiv:2501.17445,

    arXiv

  3. [11]

    Peng 45 19 Nicolas Bousquet, Laurent Feuilloley, and Théo Pierron

    S. Peng 45 19 Nicolas Bousquet, Laurent Feuilloley, and Théo Pierron. How local constraints influence network diameter and applications to lcl generalizations.arXiv preprint arXiv:2409.01305,

    arXiv

  4. [12]

    Local problems on trees from the perspectives of distributed algorithms, finitary factors, and descriptive combinatorics.arXiv preprint arXiv:2106.02066,

    20 Sebastian Brandt, Yi-Jun Chang, Jan Grebík, Christoph Grunau, Václav Rozhoň, and Zoltán Vidnyánszky. Local problems on trees from the perspectives of distributed algorithms, finitary factors, and descriptive combinatorics.arXiv preprint arXiv:2106.02066,

    arXiv

  5. [13]

    The randomized local computation complexity of the lovász local lemma

    21 Sebastian Brandt, Christoph Grunau, and Václav Rozhoň. The randomized local computation complexity of the lovász local lemma. InProceedings of the 2021 ACM Symposium on Principles of Distributed Computing, pages 307–317,

    2021

  6. [14]

    The complexity landscape of distributed locally checkable problems on trees

    24 Yi-Jun Chang. The complexity landscape of distributed locally checkable problems on trees. arXiv preprint arXiv:2009.09645,

    2009 arXiv

  7. [15]

    The distributed complexity of locally checkable labeling problems beyond paths and trees.arXiv preprint arXiv:2311.06726,

    25 Yi-Jun Chang. The distributed complexity of locally checkable labeling problems beyond paths and trees.arXiv preprint arXiv:2311.06726,

    arXiv

  8. [16]

    Local problems in trees across a wide range of distributed models.arXiv preprint arXiv:2409.13795,

    29 Anubhav Dhar, Eli Kujawa, Henrik Lievonen, Augusto Modanese, Mikail Muftuoglu, Jan Studen` y, and Jukka Suomela. Local problems in trees across a wide range of distributed models.arXiv preprint arXiv:2409.13795,

    arXiv

  9. [17]

    Non-local probes do not help with graph problems.arXiv preprint arXiv:1512.05411,

    30 Mika Göös, Juho Hirvonen, Reut Levi, Moti Medina, and Jukka Suomela. Non-local probes do not help with graph problems.arXiv preprint arXiv:1512.05411,

    arXiv

  10. [18]

    The landscape of distributed complexities on trees and beyond

    32 Christoph Grunau, Václav Rozhoň, and Sebastian Brandt. The landscape of distributed complexities on trees and beyond. InProceedings of the 2022 ACM Symposium on Principles of Distributed Computing, pages 37–47,

    2022

  11. [19]

    Shared randomness in locally checkable problems: The role of computational assumptions

    33 Adar Hadad and Moni Naor. Shared randomness in locally checkable problems: The role of computational assumptions. In28th International Conference on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2025 and the 29th International Conference on Random...

    2025

  12. [20]

    Constructing low-redundancy codes via distributed graph coloring.arXiv preprint arXiv:2512.04197,

    36 Yuting Li, Ryan Gabrys, and Farzad Farnoud. Constructing low-redundancy codes via distributed graph coloring.arXiv preprint arXiv:2512.04197,

  13. [21]

    Fast local computation algorithms

    42 Ronitt Rubinfeld, Gil Tamir, Shai Vardi, and Ning Xie. Fast local computation algorithms. arXiv preprint arXiv:1104.1377,

    arXiv

  14. [22]

    Lcls beyond bounded degrees.arXiv preprint arXiv:2602.02340,

    43Gustav Schmid. Lcls beyond bounded degrees.arXiv preprint arXiv:2602.02340,

    arXiv

  15. [23]

    An algebraic approach to borel csps.arXiv preprint arXiv:2203.16712,

    44 Riley Thornton. An algebraic approach to borel csps.arXiv preprint arXiv:2203.16712,

    arXiv

  16. [24]

    Distributedconstraint satisfaction for formalizing distributed problem solving

    45 MakotoYokoo, ToruIshida, EdmundHDurfee, andKazuhiroKuwabara. Distributedconstraint satisfaction for formalizing distributed problem solving. In[1992] Proceedings of the 12th International Conference on Distributed Computing Systems, pages 614–621. IEEE, 1992

    1992

Pith tools

Reviewed July 13, 2026 · model on record in the stance chip above.