Pith. sign in

REVIEW 1 major objections 1 minor 1 cited by

The local complexity of certifying parity

T0 review · 1 major / 1 minor · reviewed 2026-06-28 · grok-4.3

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

Pith's one-line read Parity of network size can be certified with constant bits using identifiers at radius 2 or in bounded-expansion classes, but requires Ω(log log* n) bits in anonymous radius-1 general graphs.

desk verdict The paper maps a clean landscape for parity certification: constant bits with radius 2 in ID graphs, Omega(log log* n) in anonymous radius-1 graphs, and constant again in bounded-expansion classes. read the letter →

arxiv 2606.04934 v1 pith:CQ4Y5LWN submitted 2026-06-03 cs.DC

Nicolas Bousquet , Laurent Feuilloley , Jorge Valenzuela , Sébastien Zeitoun This is my paper · ORCID
classification cs.DC
keywords localcertificationparitydistributedverificationanonymousnetworksboundedexpansioncertificatecomplexityradiusRamseyarguments
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 establishes a trichotomy for the local certification of parity across models and graph families. With unique node identifiers and verification radius 2, a constant number of bits per node suffices to certify that the total number of nodes is even. In anonymous networks restricted to radius-1 verification, however, the certificate size must grow at least as Ω(log log* n) on general graphs. The same lower bound disappears in bounded-expansion classes, where constant-size certificates again work under the stricter anonymous radius-1 rules.

What carries the argument

A lower-bound technique that constructs complex graph topologies and invokes higher-order Ramsey-type arguments to force large certificates, combined with an encoding that implicitly assigns each node a parent pointer using a constant number of bits via identifiers and conflict-free colorings.

What would settle it

An explicit constant-size certificate scheme that correctly certifies parity on every anonymous graph at verification radius 1, or a concrete family of graphs where the Ramsey-type construction fails to produce the claimed size lower bound.

Watch

Extended reading notes

Core claim

Parity certification exhibits three distinct regimes: constant-size certificates suffice when identifiers are present and verification reaches distance 2; Ω(log log* n) bits are necessary in fully anonymous graphs at radius 1; and constant-size certificates are again possible in any bounded-expansion class even without identifiers and at radius 1. These results are obtained by a new method for encoding a parent pointer at each node with constantly many bits and by a lower-bound argument that deploys complex topologies together with higher-order Ramsey-type combinatorial arguments.

Load-bearing premise

The combinatorial argument that deploys complex topologies and higher-order Ramsey-type reasoning correctly forces any anonymous radius-1 certification of parity to use certificates of size Ω(log log* n).

Editorial extensions

If this is right

  • Identifiers plus one extra verification hop reduce parity certification to constant bits on arbitrary graphs.
  • Anonymous radius-1 certification of parity on general graphs requires certificates whose bit length grows with Ω(log log* n).
  • Every bounded-expansion class admits constant-size anonymous radius-1 certificates for parity.
  • The parent-pointer encoding technique can be reused to certify tree structures or other local consistency properties with small certificates.
  • Higher-order Ramsey arguments provide a new combinatorial tool for proving certificate-size lower bounds in local verification.

Reading between the lines

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

  • The jump from radius 1 to radius 2 can collapse certificate size for global counting properties even when identifiers are absent.
  • Many other modular or counting properties that are hard in general graphs may admit constant-size certificates inside bounded-expansion classes.
  • The new Ramsey-style lower-bound method could separate certificate sizes for additional arithmetic predicates beyond parity.
  • Whether a graph class admits small parity certificates may serve as a practical test for the bounded-expansion property.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

1 major / 1 minor

Summary. The paper studies local certification of the parity property (network size congruent to a fixed value) across models. It claims that in general graphs with unique identifiers and verification radius 2, constant-size certificates suffice; in anonymous graphs with radius 1, Ω(log log* n) bits are required via a new technique using complex topologies and higher-order Ramsey arguments; and in bounded-expansion classes (e.g., bounded-degree or planar graphs), constant-size certificates exist even in the anonymous radius-1 model. New tools are introduced for encoding a parent pointer at each node using constant bits (via implicit IDs and conflict-free colorings).

Significance. If the central claims hold, the work establishes a nuanced separation for a basic global property, showing how identifiers, verification radius, and graph class restrictions interact with certification size. The new lower-bound technique based on higher-order Ramsey arguments and the parent-encoding method are explicit strengths that could transfer to other local certification problems; the paper grounds results in independent combinatorial arguments rather than fitted parameters.

major comments (1)
  1. [lower-bound technique (complex topologies and higher-order Ramsey arguments)] The section presenting the Ω(log log* n) lower bound: the reduction must explicitly map every possible radius-1 certificate assignment (including those that might encode global parity via distribution patterns alone) onto a combinatorial object whose size is forced below by the higher-order Ramsey number; without this explicit mapping shown for arbitrary certificate functions, the bound does not necessarily apply to all certificate structures.
minor comments (1)
  1. [Abstract] Abstract: states the three main results and new tools but supplies no proof sketches, certificate constructions, or verification steps for the Ramsey arguments, which hinders immediate assessment of soundness.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the positive evaluation of the paper's significance and for highlighting the contributions of the new lower-bound technique and parent-encoding method. We address the single major comment below.

read point-by-point responses

  1. Referee: [lower-bound technique (complex topologies and higher-order Ramsey arguments)] The section presenting the Ω(log log* n) lower bound: the reduction must explicitly map every possible radius-1 certificate assignment (including those that might encode global parity via distribution patterns alone) onto a combinatorial object whose size is forced below by the higher-order Ramsey number; without this explicit mapping shown for arbitrary certificate functions, the bound does not necessarily apply to all certificate structures.

    Authors: The lower-bound argument is constructed precisely to apply to an arbitrary certificate assignment function. We begin by fixing any function that, in the anonymous radius-1 model, assigns certificates of size o(log log* n) to each node on the basis of its closed neighborhood. This function induces, on any graph we later construct, a labeling of the vertices by the (finitely many) possible certificate strings. The complex topologies are then built so that their vertex sets can be partitioned into a constant number of classes whose induced subgraphs admit higher-order Ramsey numbers large enough to guarantee a large monochromatic clique (or analogous uniform substructure) under any such labeling. Inside that monochromatic substructure we embed a parity gadget whose local views are identical under the certificate function, yet whose global parity differs from the one the certificates are required to certify. Because the Ramsey extraction depends only on the existence of the labeling and not on any particular way the labels were chosen (including distribution patterns across the graph), the contradiction holds for every possible certificate function of sub-log-log* size. The mapping from certificate function to combinatorial object is therefore the induced labeling itself, which is defined for arbitrary functions. revision: no

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; derivation self-contained via new combinatorial tools

full rationale

The paper's central claims rest on explicit constructions (constant-bit parent encoding via IDs and conflict-free colorings) and a new lower-bound technique (complex topologies + higher-order Ramsey arguments) introduced in the present work. No load-bearing step reduces by definition, fitted parameter, or self-citation chain to the target result; the Ω(log log* n) bound in the anonymous radius-1 model is derived from an independent combinatorial argument that does not presuppose the certificate size it bounds. Upper bounds in other models are likewise direct constructions. The derivation is therefore self-contained against external benchmarks and receives the default non-circularity finding.

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

No free parameters or invented entities appear in the abstract; the work relies on standard graph-theoretic and combinatorial assumptions plus the established local-certification model.

assumptions (1)
  • domain assumption Standard definitions of local certification with verification radius r in the distributed computing model
    The results are stated inside the existing framework of certificate-based local verification.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The local complexity of certifying parity." pith.science (2026). https://pith.science/paper/CQ4Y5LWN

@misc{pith2026260604934,
  author       = {Pith},
  title        = {Pith review of: The local complexity of certifying parity},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CQ4Y5LWN}},
  note         = {Machine review of arXiv:2606.04934}
}
abstract

In this paper, we consider the problem of locally certifying that the size of a network is even, or more generally, congruent to some fixed number. The parity property is one of the simplest global properties, and it plays an intriguing role in local certification. On the one hand, it is one of the simplest properties in cycles because it is equivalent to 2-colorability, and hence can be certified with a single bit. On the other hand, in general graphs, no non-trivial lower bound on the size of the certificates is known, and the known upper bound basically consists in certifying the \emph{exact} value of $n$. In addition, the nature of the problem makes all the known lower bound approaches fail. We uncover a surprising landscape for parity across different models and graph structures: * In general graphs equipped with identifiers, when allowing verification radius 2, parity can be certified with a constant number of bits. * But in the model of anonymous graphs and allowing verification radius only 1, parity requires $\Omega(\log \log^*n)$ bits. * Finally, in bounded expansion graph classes (such as bounded-degree graphs and planar graphs), the lower bound does not apply: in the same restricted model we can design a constant-size certification. We introduce several new tools that we expect to be useful in other contexts, in particular ways to \emph{encode a parent at each node with a constant number of bits} (via implicit use of the IDs and conflict-free colorings) and a new lower bound technique, with complex topologies and higher-order Ramsey-type arguments.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Local Certification of Vertex and Edge Connectivity

    cs.DC 2026-07 conditional novelty 7.0 of 10

    For k≥3, certifying k-edge-connectivity requires and admits Θ(k log n)-bit labels, while k-vertex-connectivity gets O(k^3√n log^{2.5} n)-bit certificates (unconditionally for k=4, under the Itai–Zehavi conjecture for k≥5).

Reference graph

Works this paper leans on

14 extracted references · 14 canonical work pages · cited by 1 Pith paper

  1. [1]

    Optimal local certification on graphs of bounded pathwidth

    1 Dan Alden Baterisna and Yi-Jun Chang. Optimal local certification on graphs of bounded pathwidth. InProceedings of the ACM Symposium on Principles of Distributed Computing, PODC 2025, pages 99–109. ACM, 2025.doi:10.1145/3732772.3733503. 2 Lélia Blin, Fedor V. Fomin, Pierre Fraigniaud, Sylvain Gay, Petr A. Golovach, Pedro Monteale- gre, Ivan Rapaport, an...

    work page doi:10.1145/3732772.3733503 2025

  2. [2]

    Local certification of forbidden subgraphs.CoRR, abs/2402.12148,

    3 Nicolas Bousquet, Linda Cook, Laurent Feuilloley, Théo Pierron, and Sébastien Zeitoun. Local certification of forbidden subgraphs.CoRR, abs/2402.12148,

    work page arXiv

  3. [3]

    Local certification of forbidden subgraphs.CoRR, abs/2402.12148,

    URL: https: //doi.org/10.48550/arXiv.2402.12148,doi:10.48550/ARXIV.2402.12148. 4 Nicolas Bousquet, Laurent Feuilloley, and Sébastien Zeitoun. Complexity landscape for local certification. In39th International Symposium on Distributed Computing, DISC 2025, LIPIcs, pages 18:1–18:21,

    work page doi:10.48550/arxiv.2402.12148 2025

  4. [4]

    5 Nicolas Bousquet, Laurent Feuilloley, and Sébastien Zeitoun

    URL: https://doi.org/10.4230/LIPIcs.DISC.2025.18, doi:10.4230/LIPICS.DISC.2025.18. 5 Nicolas Bousquet, Laurent Feuilloley, and Sébastien Zeitoun. Local certification of local properties: Tight bounds, trade-offs, and new parameters.SIAM J. Discret. Math., 39(4):1974– 2002,

    work page doi:10.4230/lipics.disc.2025.18 2025

  5. [5]

    6Jérémie Chalopin, Victor Chepoi, and Maria Kokkou

    URL:https://doi.org/10.1137/24m1650041,doi:10.1137/24M1650041. 6Jérémie Chalopin, Victor Chepoi, and Maria Kokkou. Distance-based certification for leader election in meshed graphs and local recognition of their subclasses.CoRR, abs/2602.12894,

    work page doi:10.1137/24m1650041

  6. [6]

    7 LindaCook, EunJungKim, andTomásMasarík

    URL:https://doi.org/10.48550/arXiv.2602.12894,doi:10.48550/ARXIV.2602.12894. 7 LindaCook, EunJungKim, andTomásMasarík. Atightmeta-theoremforLOCALcertification of MSO2 properties within bounded treewidth graphs. InProceedings of the ACM Symposium on Principles of Distributed Computing, PODC 2025, pages 110–120. ACM,

    work page doi:10.48550/arxiv.2602.12894 2025

  7. [7]

    8 Laurent Feuilloley

    doi: 10.1145/3732772.3733562. 8 Laurent Feuilloley. Introduction to local certification.Discret. Math. Theor. Comput. Sci., 23(3),

    work page doi:10.1145/3732772.3733562

  8. [8]

    9 Laurent Feuilloley, Nicolas Bousquet, and Théo Pierron

    URL:https://doi.org/10.46298/dmtcs.6280,doi:10.46298/DMTCS.6280. 9 Laurent Feuilloley, Nicolas Bousquet, and Théo Pierron. What can be certified compactly? compact local certification of MSO properties in tree-like graphs. In Alessia Milani and Philipp Woelfel, editors,PODC ’22: ACM Symposium on Principles of Distributed Computing, pages 131–140. ACM, 202...

    work page doi:10.46298/dmtcs.6280 2022

Show all 14 references
  1. [9]

    1007/S00453-021-00823-W

    URL: https://doi.org/10.1007/s00453-021-00823-w, doi:10. 1007/S00453-021-00823-W. 11 Laurent Feuilloley, Josef Erik Sedlácek, and Martin Slávik. Proving there is a leader without naming it. InSIROCCO ’26, page To Appear,

    doi

  2. [10]

    12 Arnold Filtser and Orr Fischer

    arxiv: 2511.15491. 12 Arnold Filtser and Orr Fischer. Near-resolution of the tradeoff conjecture in distributed proof labeling schemes. InPODC ’26, page To Appear,

  3. [11]

    13 Pierre Fraigniaud, Frédéric Mazoit, Pedro Montealegre, Ivan Rapaport, and Ioan Todinca

    arxiv: 2605.19078. 13 Pierre Fraigniaud, Frédéric Mazoit, Pedro Montealegre, Ivan Rapaport, and Ioan Todinca. Distributed certification for classes of dense graphs. In37th International Symposium on Distributed Computing, DISC 2023, LIPIcs, pages 20:1–20:17. Schloss Dagstuhl -...

    2023 arXiv

  4. [12]

    14 Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, and Ioan Todinca

    URL:https://doi.org/10.4230/LIPIcs.DISC.2023.20, doi: 10.4230/LIPICS.DISC.2023.20. 14 Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, and Ioan Todinca. A meta-theorem for distributed certification.Algorithmica, 86(2):585–612,

    2023 doi

  5. [13]

    1007/s00453-023-01185-1,doi:10.1007/S00453-023-01185-1

    URL:https://doi.org/10. 1007/s00453-023-01185-1,doi:10.1007/S00453-023-01185-1. 15 Mika Göös and Jukka Suomela. Locally checkable proofs in distributed computing.Theory Comput., 12(1):1–33, 2016.doi:10.4086/TOC.2016.V012A019. 16 Ronald L Graham, Bruce L Rothschild, and Joel H ...

    2016 doi

  6. [14]

    19 Moni Naor and Larry J

    URL:https://doi.org/10.1007/s00446-010-0095-3, doi:10.1007/ S00446-010-0095-3. 19 Moni Naor and Larry J. Stockmeyer. What can be computed locally?SIAM J. Comput., 24(6):1259–1277, 1995.doi:10.1137/S0097539793254571. 20 Yudi Setyawan.Combinatorial Number Theory: Results of Hilb...

    1995 doi

Pith tools

Reviewed June 28, 2026 · model on record in the stance chip above.