Pith. sign in

REVIEW 2 major objections 5 minor 43 references

Complexity landscape for local certification

T0 review · 2 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read Anonymous path certification has a hard gap: every sub-log-log-bit scheme collapses to constant size, while a natural language needs exactly $\Theta(\log\log n)$.

desk verdict Genuinely new gap theorems for anonymous local certification, with a real but peripheral flaw in Theorem 1 that should be fixed before publication. read the letter →

arxiv 2505.20915 v1 pith:2CLUNWMW submitted 2025-05-27 cs.DC cs.DMcs.DS

Nicolas Bousquet , Laurent Feuilloley , Sébastien Zeitoun This is my paper
classification cs.DCcs.DMcs.DS MSC 68Q4568W15
keywords localcertificationproof-labelingschemeslocallycheckableproofsspacecomplexitydistributedgraphalgorithmsgapanonymousnetworksautomatatheory
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

The paper initiates a complexity-landscape study for the space used by distributed local certification, asking which certificate sizes can actually occur. On anonymous paths it establishes the first gap in this setting: for any $c>1$, a property certifiable with certificates of size $\lfloor(\log\log n)/c\rfloor$ bits for all large $n$ is in fact certifiable with $O(1)$ bits, and there is a concrete property (paths whose length is not a product of consecutive primes) whose optimal certificate size is exactly $\Theta(\log\log n)$. On anonymous cycles the gap is wider, between $O(1)$ and $\Theta(\log n)$, and on trees of unbounded degree with verification radius 1 it reappears as a gap between $O(1)$ and $\Theta(\log\log d)$, where $d$ is the diameter. The paper also proves several 'no gap' settings, showing that when nodes have identifiers in $[1,n]$, exact knowledge of $n$, or a larger verification radius, every well-behaved function is the optimal certificate size of some property. The anonymity and absence of global size knowledge are therefore load-bearing premises for the gap results.

What carries the argument

The load-bearing objects are finite automata built from certification schemes: for each certificate size $k$, one forms an automaton (or a directed certificate graph whose closed walks are accepted cycles) whose states are pairs of certificates, so that an accepting run of length $t$ corresponds exactly to a $t$-vertex path (or cycle) accepted with size-$k$ certificates. The path proofs then combine three automata-theoretic facts: the state-complexity bounds of Lemma 17 for unions, intersections, and complements; the Chrobak normal form for unary automata, which decomposes every such automaton into a short path plus disjoint cycles whose lengths sum to at most the number of states; and Landau's function $g(n)\sim e^{\sqrt{n\ln n}}$ to bound the lcm of those cycle lengths. The cycle proof uses a generalized B\'ezout identity (Lemma 27) on the lengths of elementary cycles of the certificate graph, and the tree proof uses automata whose transitions are labeled by rooted trees, together with a 'no repeated state in a minimal run' argument that bounds the diameter by the number of states.

What would settle it

Exhibit a property of anonymous paths whose optimal certificate size is provably $\omega(1)$ and $o(\log\log n)$ (for instance exactly $\Theta(\log\log\log n)$); Theorem 5 rules such a property out, so a correct construction with a matching lower bound would refute the path gap. Equivalently, find an eventually non-periodic set of lengths $S$ admitting a constant-size certification, contradicting Observation 45.

Watch

Extended reading notes

Core claim

The central discovery is that the space complexity of local certification on anonymous path-like graphs is not a continuum but has sharp thresholds. For paths, the automata associated with certificates of size $k$ have $2^{2^k}+2$ states, and an automata-theoretic state-complexity argument shows that if a language first becomes recognizable at certificate size $k$ then it has an accepting instance of length at most doubly exponential in $k$; hence any property with certificates of size $o(\log\log n)$ collapses to constant size. The threshold is tight: the set of paths whose length is not $\prod_{i\le k} p_i$ for any $k$ can be certified with $O(\log\log n)$ bits and cannot be certified with $O(1)$ bits, because constant-size certification is equivalent to an eventually periodic set of lengths. For cycles the same translation into closed walks of certificate graphs, combined with a generalized B\'ezout identity, yields the stronger collapse of any sublogarithmic certificate size, with 'length is not a power of two' realizing the $\Theta(\log n)$ threshold. For trees, parsing a tree as a sequence of rooted subtrees along a longest path turns the argument into one about automata with an infinite alphabet, yielding a gap between $O(1)$ and $\Theta(\log\log d)$ when the verification radius is 1.

Load-bearing premise

The gap theorems assume the nodes are anonymous and have no usable knowledge of the total number of nodes $n$, and for the tree result that each node inspects only its immediate neighborhood; the paper shows these assumptions are essential, since giving nodes identifiers in $[1,n]$, exact or sharp estimates of $n$, or a larger verification radius makes the gaps disappear.

Editorial extensions

If this is right

  • Any anonymous-path property certifiable with $o(\log\log n)$ bits is certifiable with $O(1)$ bits; consequently no complexity occurs strictly between $O(1)$ and $\Theta(\log\log n)$ in this setting, and the consecutive-prime-product language realizes the boundary.
  • On anonymous cycles, every $o(\log n)$-bit certification collapses to constant size, and 'length is not a power of two' realizes the $\Theta(\log n)$ boundary.
  • For trees of unbounded degree with verification radius 1, every $o(\log\log d)$-bit certification collapses to constant size as a function of diameter $d$.
  • With identifiers in $[1,n]$, exact knowledge of $n$, or verification radius at least 2 on caterpillars, the gaps vanish: every well-behaved nondecreasing function is the optimal certificate size of some property.
  • Constant-size certification on anonymous paths characterizes exactly the eventually periodic sets of lengths, so the bottom of the space-complexity landscape has a clean arithmetic shape.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The automata translation suggests that the same gap phenomenon should be sought in any graph class whose local views can be linearized into a path-like walk; grids, graphs of bounded pathwidth, and directed variants are natural places where a similar state-complexity bound might yield new thresholds.
  • The consecutive-prime construction suggests a family of languages indexed by the density of the prime set: by thinning the primes used, the optimal certificate size may interpolate between $\log\log n$ and $\log n$; a concrete testable step is to analyse the certification complexity of 'length is not a product of every $\ell$-th prime'.
  • Since a sharp estimate of $n$ creates non-constant sub-$\log\log n$ properties, the gap is best understood as an uncertainty effect: if one could give anonymous nodes any verifiable global-size information, one would expect the landscape below $\log\log n$ to become dense rather than gapped.
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

2 major / 5 minor

Summary. The paper initiates a complexity-landscape study for local certification, focusing on certificate size as a function of the input size. For anonymous unlabeled paths, it proves a gap between constant-size certificates and Θ(log log n): any property certifiable with ⌊log log n / c⌋ bits for c > 1 is constant-size certifiable (Theorem 5), and a concrete property (paths whose length is not a product of consecutive primes) has optimal size Θ(log log n) (Theorem 6). On cycles the gap is between O(1) and Θ(log n) (Theorem 7). For trees with verification radius 1 and diameter d, the path gap generalizes to Θ(log log d) (Theorem 8). The paper also gives no-gap results for general graphs with identifiers (Theorem 1), for caterpillars (Theorems 9 and 10), and for general graphs via caterpillars (Theorem 50), and it analyzes how identifiers and knowledge of n destroy or preserve the gaps (Section 15).

Significance. Assuming the main proofs are correct, this is a substantial contribution. It establishes the first gap in local certification complexity, introduces a natural intermediate Θ(log log n) regime, and identifies an exponential separation between paths and cycles. The toolkit — automata and state complexity, Chrobak normal form, Landau's function, the prime number theorem, and Brauer's lemma — is likely to be reused. The central proofs of Theorems 5–8 are detailed and coherent, and the main gap theorems do not depend on the sketched peripheral results. The paper is honest about which parts are sketches, but two of those sketched results, Theorem 1 and Theorem 53, need further work before they can be considered established.

major comments (2)
  1. [11 (Theorem 1)] The upper-bound accounting in the proof of Theorem 1 is incorrect at the endpoint f(n)=Θ(log n). The certificate contains the adjacency matrix of H, which costs O(f(n)) bits, plus the identifier assignment restricted to the two copies, which the proof itself states costs 2√f(n)·log n bits. For f(n)=Θ(log n) this is Θ((log n)^{3/2}), not O(log n), and no alternative encoding is provided. Thus the claimed range Ω(log n) ∩ O(n^2) is not established. Since Theorem 1 is announced as the motivation for the 'no gap above log n' part of the landscape, this must be fixed, either by supplying a proof that handles f(n)=Θ(log n) (for example by distributing the encoding of H and the identifiers so that each node uses only O(log n) bits) or by restricting the theorem's range to, say, Ω(log^2 n). The central gap theorems (5–8) do not depend on Theorem 1, but the theorem as stated is part of the paper's claims.
  2. [15.3 (Theorem 53)] The proof of Theorem 53 is only a sketch, and its key uniformity step is not justified. The claim that, for each certificate size s, there is an infinite identifier set I_s on which the accept/reject mapping is invariant is supported only by the observation that the number of certificate-pattern mappings is bounded by a function of s. That bound does not account for verification functions that use arithmetic relations between identifiers (such as comparisons or differences), so the number of identifier-dependent behaviors need not be finite. The theorem that arbitrarily large identifiers do not help is therefore not proved as written. Please expand the proof or weaken/qualify the statement.
minor comments (5)
  1. [4 (Lemma 19)] There is a typo in the proof: the second sentence should say that the prover writes d_u mod m in Distance[u], rather than repeating Orientation[u].
  2. [5.2 (Proof of Theorem 7)] In the final application of Lemma 27, 'apd + bpd = n_k' should read 'apd + bqd = n_k'.
  3. [10 (Proof of Theorem 5)] In the sentence 'By assumption on n_k ... we have n_k−pM_k!∈...', the expression 'pM_k!' is a typo and should be 'p_k'.
  4. [15.1 (Theorem 51)] The identifier case is too compressed: it is not explained how a node that does not know n can check whether it is within distance f(n) of an endpoint, or how f(n) is inferred from identifiers in [1,n]. Please expand this part of the proof.
  5. [15.2 (Theorem 52)] The derivation of the interval [n̂−g(n̂)−1, n̂+g(n̂)+1] and the use of a counter modulo 4g(n) need a more explicit treatment: the nodes only know n̂, so the scheme should specify how the modulus is computed from n̂ and why the interval contains the true n for all sufficiently large n.

Circularity Check

0 steps flagged · score 1.0 of 10

No load-bearing circularity; the path/cycle/tree gap theorems rest on external automata and number theory, not on the paper's own conclusions.

full rationale

The central gap theorems (Theorems 5, 6, 7, 8) are derived from external mathematical tools: Chrobak normal form, Landau's function, the prime number theorem, Brauer's lemma, and standard automata state-complexity bounds. The automaton associated to a certification is constructed from the certificate assignments, not from the target property in a way that presupposes the gap. The log-log language in Theorem 6 is an independently defined arithmetic set (lengths that are not products of consecutive primes), and its non-constant lower bound follows from the eventual-periodicity characterization of constant-size certifications, which is itself proved from Chrobak normal form. No parameter is fitted to data and then renamed as a prediction; the 'no gap' constructions parameterize properties by the given function f, but that is a standard hardness construction, not circularity. Self-citations appear (e.g., [10], [14], [29]) but only as contextual pointers or as credit for constructions that are fully described in the present text; none is load-bearing. The sensitivity results (Theorems 51 and 52) show that the anonymity/no-global-knowledge assumption is essential, but that is a sensitivity statement, not a circular step. One peripheral correctness concern exists in the proof sketch of Theorem 1: the identifier encoding is said to cost 2*sqrt(f(n)) log n bits, which is not O(f(n)) at the endpoint f(n)=Theta(log n). That is a correctness gap in the announced range, not a circular reduction, and it does not affect the central gap theorems. Overall, the claimed derivations are self-contained against external benchmarks, so the circularity score is very low.

Assumptions & free parameters 0 free parameters · 7 assumptions · 0 invented entities

The paper introduces no fitted parameters; the constants c, N, r, and Δ are universal quantifiers in theorems, not tuned to data. The central claims rest on standard theorems in automata theory and number theory, listed above, and on the model definitions in Section 2.2 (anonymous nodes, certificate size s(n), verification radius r). The only novel constructions are mathematical objects such as automata over rooted trees and the sequence a_i, not invented physical entities.

assumptions (7)
  • standard math Prime Number Theorem (Theorem 25)
    Used in Corollary 26 to guarantee many primes in the interval (2^{4n+1}, 2^{n(c/2-2)}) for c>12, which drives the cycle gap proof.
  • standard math Landau's function asymptotics (Theorem 46)
    Used in Claim 47 of Theorem 5 to show g(2^{2k+1}) = o(2^{2ck}) for c>1, enabling the Chrobak-based gap.
  • standard math Chrobak normal form for unary NFA (Theorem 44)
    Underpins both the eventual-periodicity observation (Observation 45) and the proof of Theorem 5.
  • standard math Brauer's generalization of Bézout's identity (Lemma 27)
    Used in Theorem 7 and Proposition 32 to build closed walks of prescribed lengths from gcds.
  • standard math Chinese remainder theorem and the lower bound on the lcm of 1..t
    Used in Lemma 23 to find a small modulus distinguishing two integers, a key step for the Θ(log log n) language.
  • standard math Folklore state complexity bounds for union, intersection, and complement of NFA languages (Lemma 17)
    Used throughout the gap proofs to bound the size of an automaton recognizing the first 'new' lengths or parsings.
  • standard math Prime estimates p_k = Θ(k log k) and a_k = 2^{k log k(1+o(1))}
    Used in Lemma 22 and in the size analysis of the Θ(log log n) certification in Theorem 6.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Complexity landscape for local certification." pith.science (2026). https://pith.science/paper/2CLUNWMW

@misc{pith2026250520915,
  author       = {Pith},
  title        = {Pith review of: Complexity landscape for local certification},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2CLUNWMW}},
  note         = {Machine review of arXiv:2505.20915}
}
abstract

An impressive recent line of work has charted the complexity landscape of distributed graph algorithms. For many settings, it has been determined which time complexities exist, and which do not (in the sense that no local problem could have an optimal algorithm with that complexity). In this paper, we initiate the study of the landscape for space complexity of distributed graph algorithms. More precisely, we focus on the local certification setting, where a prover assigns certificates to nodes to certify a property, and where the space complexity is measured by the size of the certificates. Already for anonymous paths and cycles, we unveil a surprising landscape: - There is a gap between complexity $O(1)$ and $\Theta(\log \log n)$ in paths. This is the first gap established in local certification. - There exists a property that has complexity $\Theta(\log \log n)$ in paths, a regime that was not known to exist for a natural property. - There is a gap between complexity $O(1)$ and $\Theta(\log n)$ in cycles, hence a gap that is exponentially larger than for paths. We then generalize our result for paths to the class of trees. Namely, we show that there is a gap between complexity $O(1)$ and $\Theta(\log \log d)$ in trees, where $d$ is the diameter. We finally describe some settings where there are no gaps at all. To prove our results we develop a new toolkit, based on various results of automata theory and arithmetic, which is of independent interest.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

43 extracted references · 20 canonical work pages

  1. [1]

    Introduction to Distributed Self-Stabilizing Algorithms

    Karine Altisen, St \' e phane Devismes, Swan Dubois, and Franck Petit. Introduction to Distributed Self-Stabilizing Algorithms . Morgan & Claypool Publishers, 2019. https://doi.org/10.2200/S00908ED1V01Y201903DCT015 doi:10.2200/S00908ED1V01Y201903DCT015

    work page doi:10.2200/s00908ed1v01y201903dct015 2019

  2. [2]

    An introduction to population protocols

    James Aspnes and Eric Ruppert. An introduction to population protocols. Bull. EATCS , 93:98--117, 2007

    work page 2007

  3. [3]

    The distributed complexity of locally checkable problems on paths is decidable

    Alkida Balliu, Sebastian Brandt, Yi - Jun Chang, Dennis Olivetti, Mika \" e l Rabie, and Jukka Suomela. The distributed complexity of locally checkable problems on paths is decidable. In Peter Robinson and Faith Ellen, editors, Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019 , pages 262--271. ACM , 2019. https://doi...

    arXiv 2019

  4. [4]

    Efficient classification of locally checkable problems in regular trees

    Alkida Balliu, Sebastian Brandt, Yi - Jun Chang, Dennis Olivetti, Jan Studen \' y , and Jukka Suomela. Efficient classification of locally checkable problems in regular trees. In Christian Scheideler, editor, 36th International Symposium on Distributed Computing, DISC 2022 , volume 246 of LIPIcs , pages 8:1--8:19, 2022. https://doi.org/10.4230/LIPICS.DISC...

    doi:10.4230/lipics.disc.2022.8 2022

  5. [5]

    Locally checkable problems in rooted trees

    Alkida Balliu, Sebastian Brandt, Yi - Jun Chang, Dennis Olivetti, Jan Studen \' y , Jukka Suomela, and Aleksandr Tereshchenko. Locally checkable problems in rooted trees. Distributed Comput. , 36(3):277--311, 2023. https://doi.org/10.1007/S00446-022-00435-9 doi:10.1007/S00446-022-00435-9

    work page doi:10.1007/s00446-022-00435-9 2023

  6. [6]

    Almost global problems in the LOCAL model

    Alkida Balliu, Sebastian Brandt, Dennis Olivetti, and Jukka Suomela. Almost global problems in the LOCAL model. Distributed Comput. , 34(4):259--281, 2021. https://doi.org/10.1007/S00446-020-00375-2 doi:10.1007/S00446-020-00375-2

    doi:10.1007/s00446-020-00375-2 2021

  7. [7]

    Korhonen, Tuomo Lempi \" a inen, Dennis Olivetti, and Jukka Suomela

    Alkida Balliu, Juho Hirvonen, Janne H. Korhonen, Tuomo Lempi \" a inen, Dennis Olivetti, and Jukka Suomela. New classes of distributed time complexity. In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018 , pages 1307--1318. ACM , 2018. https://doi.org/10.1...

    arXiv 2018

  8. [8]

    Optimal local certification on graphs of bounded pathwidth

    Dan Alden Baterisna and Yi - Jun Chang. Optimal local certification on graphs of bounded pathwidth. CoRR , abs/2502.00676, 2025. URL: https://doi.org/10.48550/arXiv.2502.00676, https://arxiv.org/abs/2502.00676 arXiv:2502.00676 , https://doi.org/10.48550/ARXIV.2502.00676 doi:10.48550/ARXIV.2502.00676

    work page Pith review arXiv doi:10.48550/arxiv.2502.00676 2025

Show all 43 references
  1. [9]

    Memory space requirements for self-stabilizing leader election protocols

    Joffroy Beauquier, Maria Gradinariu, and Colette Johnen. Memory space requirements for self-stabilizing leader election protocols. In Proceedings of the Eighteenth Annual ACM Symposium on Principles of Distributed Computing, PODC'99 , pages 199--207. ACM , 1999. https://doi.or...

    1999

  2. [10]

    Silent MST approximation for tiny memory

    L \' e lia Blin, Swan Dubois, and Laurent Feuilloley. Silent MST approximation for tiny memory. In St \' e phane Devismes and Neeraj Mittal, editors, Stabilization, Safety, and Security of Distributed Systems - 22nd International Symposium, SSS 2020 , volume 12514, pages 118--...

    2020 doi

  3. [11]

    On proof-labeling schemes versus silent self-stabilizing algorithms

    L \' e lia Blin, Pierre Fraigniaud, and Boaz Patt - Shamir. On proof-labeling schemes versus silent self-stabilizing algorithms. In Stabilization, Safety, and Security of Distributed Systems - 16th International Symposium, SSS 2014 , volume 8756, pages 18--32, 2014. https://do...

    2014 doi

  4. [12]

    Local certification of forbidden subgraphs

    Nicolas Bousquet, Linda Cook, Laurent Feuilloley, Th \' e o Pierron, and S \' e bastien Zeitoun. Local certification of forbidden subgraphs. CoRR , abs/2402.12148, 2024. URL: https://doi.org/10.48550/arXiv.2402.12148, https://arxiv.org/abs/2402.12148 arXiv:2402.12148 , https:/...

    2024 doi arXiv

  5. [13]

    Renaming in distributed certification

    Nicolas Bousquet, Louis Esperet, Laurent Feuilloley, and S \' e bastien Zeitoun. Renaming in distributed certification. CoRR , abs/2409.15404, 2024. URL: https://doi.org/10.48550/arXiv.2409.15404, https://doi.org/10.48550/ARXIV.2409.15404 doi:10.48550/ARXIV.2409.15404

    2024 doi

  6. [14]

    How local constraints influence network diameter and applications to LCL generalizations

    Nicolas Bousquet, Laurent Feuilloley, and Th \' e o Pierron. How local constraints influence network diameter and applications to LCL generalizations. In 28th International Conference on Principles of Distributed Systems, OPODIS 2024 , volume 324 of LIPIcs , pages 28:1--28:28,...

    2024 doi

  7. [15]

    Local certification of local properties: Tight bounds, trade-offs and new parameters

    Nicolas Bousquet, Laurent Feuilloley, and S \' e bastien Zeitoun. Local certification of local properties: Tight bounds, trade-offs and new parameters. In 41st International Symposium on Theoretical Aspects of Computer Science, STACS 2024 , volume 289 of LIPIcs , pages 21:1--2...

    2024 doi

  8. [16]

    A lower bound for the distributed lov \' a sz local lemma

    Sebastian Brandt, Orr Fischer, Juho Hirvonen, Barbara Keller, Tuomo Lempi \" a inen, Joel Rybicki, Jukka Suomela, and Jara Uitto. A lower bound for the distributed lov \' a sz local lemma. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016...

    2016

  9. [17]

    a inen, Patric R. J. \

    Sebastian Brandt, Juho Hirvonen, Janne H. Korhonen, Tuomo Lempi \" a inen, Patric R. J. \" O sterg rd, Christopher Purcell, Joel Rybicki, Jukka Suomela, and Przemyslaw Uznanski. LCL problems on grids. In Elad Michael Schiller and Alexander A. Schwarzmann, editors, Proceedings ...

    2017

  10. [18]

    On a problem of partitions

    Alfred Brauer. On a problem of partitions. American Journal of Mathematics , 64(1):299--312, 1942

    1942

  11. [19]

    Approximate proof-labeling schemes

    Keren Censor - Hillel, Ami Paz, and Mor Perry. Approximate proof-labeling schemes. Theor. Comput. Sci. , 811:112--124, 2020. URL: https://doi.org/10.1016/j.tcs.2018.08.020, https://doi.org/10.1016/J.TCS.2018.08.020 doi:10.1016/J.TCS.2018.08.020

    2020 doi

  12. [20]

    The complexity landscape of distributed locally checkable problems on trees

    Yi - Jun Chang. The complexity landscape of distributed locally checkable problems on trees. In Hagit Attiya, editor, 34th International Symposium on Distributed Computing, DISC 2020 , volume 179 of LIPIcs , pages 18:1--18:17, 2020. https://doi.org/10.4230/LIPICS.DISC.2020.18 ...

    2020 doi

  13. [21]

    The distributed complexity of locally checkable labeling problems beyond paths and trees

    Yi - Jun Chang. The distributed complexity of locally checkable labeling problems beyond paths and trees. In 15th Innovations in Theoretical Computer Science Conference, ITCS 2024, January 30 to February 2, 2024, Berkeley, CA, USA , volume 287 of LIPIcs , pages 26:1--26:25, 20...

    2024 doi

  14. [22]

    An exponential separation between randomized and deterministic complexity in the LOCAL model

    Yi - Jun Chang, Tsvi Kopelowitz, and Seth Pettie. An exponential separation between randomized and deterministic complexity in the LOCAL model. SIAM J. Comput. , 48(1):122--143, 2019. https://doi.org/10.1137/17M1117537 doi:10.1137/17M1117537

    2019 doi

  15. [23]

    A time hierarchy theorem for the LOCAL model

    Yi - Jun Chang and Seth Pettie. A time hierarchy theorem for the LOCAL model. SIAM J. Comput. , 48(1):33--69, 2019. https://doi.org/10.1137/17M1157957 doi:10.1137/17M1157957

    2019 doi

  16. [24]

    Distributed graph problems through an automata-theoretic lens

    Yi - Jun Chang, Jan Studen \' y , and Jukka Suomela. Distributed graph problems through an automata-theoretic lens. Theor. Comput. Sci. , 951:113710, 2023. https://doi.org/10.1016/J.TCS.2023.113710 doi:10.1016/J.TCS.2023.113710

    2023

  17. [25]

    A tight meta-theorem for LOCAL certification of mso\( _ 2 \) properties within bounded treewidth graphs

    Linda Cook, Eun Jung Kim, and Tom \' a s Masar \' k. A tight meta-theorem for LOCAL certification of mso\( _ 2 \) properties within bounded treewidth graphs. CoRR , abs/2503.19671, 2025. URL: https://doi.org/10.48550/arXiv.2503.19671, https://arxiv.org/abs/2503.19671 arXiv:250...

    2025 doi

  18. [26]

    Self-Stabilization

    Shlomi Dolev. Self-Stabilization . MIT Press, 2000. URL: http://www.cs.bgu.ac.il/\

    2000

  19. [28]

    Introduction to local certification

    Laurent Feuilloley. Introduction to local certification. Discret. Math. Theor. Comput. Sci. , 23(3), 2021. URL: https://doi.org/10.46298/dmtcs.6280, https://doi.org/10.46298/DMTCS.6280 doi:10.46298/DMTCS.6280

    2021 doi

  20. [29]

    What can be certified compactly? compact local certification of MSO properties in tree-like graphs

    Laurent Feuilloley, Nicolas Bousquet, and Th \' e o Pierron. What can be certified compactly? compact local certification of MSO properties in tree-like graphs. In PODC '22: ACM Symposium on Principles of Distributed Computing , pages 131--140. ACM , 2022. https://doi.org/10.1...

    2022

  21. [30]

    Survey of distributed decision

    Laurent Feuilloley and Pierre Fraigniaud. Survey of distributed decision. Bull. EATCS , 119, 2016. URL: http://eatcs.org/beatcs/index.php/beatcs/article/view/411

    2016

  22. [31]

    What can be decided locally without identifiers? In ACM Symposium on Principles of Distributed Computing , pages 157--165

    Pierre Fraigniaud, Mika G \" o \" o s, Amos Korman, and Jukka Suomela. What can be decided locally without identifiers? In ACM Symposium on Principles of Distributed Computing , pages 157--165. ACM , 2013. https://doi.org/10.1145/2484239.2484264 doi:10.1145/2484239.2484264

    2013

  23. [32]

    Halld \' o rsson, and Amos Korman

    Pierre Fraigniaud, Magn \' u s M. Halld \' o rsson, and Amos Korman. On the impact of identifiers on local decision. In Principles of Distributed Systems, 16th International Conference, OPODIS 2012 , volume 7702, pages 224--238. Springer, 2012. https://doi.org/10.1007/978-3-64...

    2012 doi

  24. [33]

    Node labels in local decision

    Pierre Fraigniaud, Juho Hirvonen, and Jukka Suomela. Node labels in local decision. Theor. Comput. Sci. , 751:61--73, 2018. URL: https://doi.org/10.1016/j.tcs.2017.01.011, https://doi.org/10.1016/J.TCS.2017.01.011 doi:10.1016/J.TCS.2017.01.011

    2018 doi

  25. [34]

    Towards a complexity theory for local distributed computing

    Pierre Fraigniaud, Amos Korman, and David Peleg. Towards a complexity theory for local distributed computing. J. ACM , 60(5):35:1--35:26, 2013. https://doi.org/10.1145/2499228 doi:10.1145/2499228

    2013 doi

  26. [35]

    Distributed certification for classes of dense graphs

    Pierre Fraigniaud, Fr \' e d \' e ric Mazoit, Pedro Montealegre, Ivan Rapaport, and Ioan Todinca. Distributed certification for classes of dense graphs. In Rotem Oshman, editor, 37th International Symposium on Distributed Computing, DISC 2023 , volume 281 of LIPIcs , pages 20:...

    2023 doi

  27. [36]

    A meta-theorem for distributed certification

    Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, and Ioan Todinca. A meta-theorem for distributed certification. Algorithmica , 86(2):585--612, 2024. https://doi.org/10.1007/S00453-023-01185-1 doi:10.1007/S00453-023-01185-1

    2024 doi

  28. [37]

    Locally checkable proofs in distributed computing

    Mika G \" o \" o s and Jukka Suomela. Locally checkable proofs in distributed computing. Theory Comput. , 12(1):1--33, 2016. https://doi.org/10.4086/TOC.2016.V012A019 doi:10.4086/TOC.2016.V012A019

    2016 doi

  29. [38]

    An introduction to the theory of numbers

    Godfrey Harold Hardy and Edward Maitland Wright. An introduction to the theory of numbers . Oxford university press, 1979

    1979

  30. [39]

    On the computational complexity of algorithms

    Juris Hartmanis and Richard E Stearns. On the computational complexity of algorithms. Transactions of the American Mathematical Society , 117:285--306, 1965

    1965

  31. [40]

    Massively parallel computation: Algorithms and applications

    Sungjin Im, Ravi Kumar, Silvio Lattanzi, Benjamin Moseley, and Sergei Vassilvitskii. Massively parallel computation: Algorithms and applications. Found. Trends Optim. , 5(4):340--417, 2023. https://doi.org/10.1561/2400000025 doi:10.1561/2400000025

    2023 doi

  32. [41]

    Proof labeling schemes

    Amos Korman, Shay Kutten, and David Peleg. Proof labeling schemes. Distributed Comput. , 22(4):215--233, 2010. URL: https://doi.org/10.1007/s00446-010-0095-3, https://doi.org/10.1007/S00446-010-0095-3 doi:10.1007/S00446-010-0095-3

    2010 doi

  33. [42]

    Distributed complexity of p\( _ k \)-freeness: Decision and certification

    Masayuki Miyamoto. Distributed complexity of p\( _ k \)-freeness: Decision and certification. CoRR , abs/2410.20353, 2024. URL: https://doi.org/10.48550/arXiv.2410.20353, https://arxiv.org/abs/2410.20353 arXiv:2410.20353 , https://doi.org/10.48550/ARXIV.2410.20353 doi:10.48550...

    2024 doi arXiv

  34. [43]

    Rabin and Dana S

    Michael O. Rabin and Dana S. Scott. Finite automata and their decision problems. IBM J. Res. Dev. , 3(2):114--125, 1959. URL: https://doi.org/10.1147/rd.32.0114, https://doi.org/10.1147/RD.32.0114 doi:10.1147/RD.32.0114

    1959 doi

  35. [44]

    Landscape of locality (invited talk)

    Jukka Suomela. Landscape of locality (invited talk). In Susanne Albers, editor, 17th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT , volume 162 of LIPIcs , pages 2:1--2:1. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2020. https://doi.org/10.4230/LI...

    2020 doi

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.