arXiv CSopen access

The local complexity of certifying parity

The local complexity of certifying parity Nicolas Bousquet # CNRS, INSA Lyon, UCBL, LIRIS, UMR5205, F-69622 Villeurbanne, France

Laurent Feuilloley # CNRS, INSA Lyon, UCBL, LIRIS, UMR5205, F-69622 Villeurbanne, France

Jorge Valenzuela # Universidad de Chile, Santiago, Chile

Sébastien Zeitoun # CNRS, INSA Lyon, UCBL, LIRIS, UMR5205, F-69622 Villeurbanne, France

arXiv:2606.04934v1 [cs.DC] 3 Jun 2026

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 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 Ω(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 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. 2012 ACM Subject Classification Theory of computation → Distributed algorithms Keywords and phrases Local certification, proof-labeling schemes, locally checkable proofs, space complexity, parity, congruence, lower bound Funding This work is supported by the ANR grant ENEDISC (ANR-24-CE48-7768). Acknowledgements The authors would like to thank Chilian-French ECOS-Sud-ANID program for funding the trip of the third author to France.

2

The local complexity of certifying parity

1

Introduction

This paper deals with local certification, a type of labeling that allows the verification of graph properties in a distributed manner. In local certification, an all-powerful prover assigns a label to every node, referred to as the certificate of the node. Then, each node inspects its neighborhood, including the certificates, and decides to accept or reject. Such a scheme is correct if: for any graph satisfying the property, there exists a certificate assignment that makes all nodes accept, and for any graph not satisfying the property, no such assignment exists.1 Local certification, which originates from the study of fault-tolerance and self-stabilization, is now a well-established topic. We refer to [8] for an introduction to the area and provide formal definitions in Section 2. In recent years, numerous graph properties have been studied through the lens of local certification, such as planarity, bounded treewidth, forbidden subgraphs, and connectivity. However, a very simple property has been overlooked: parity, that is, the property of having an even number of nodes. In this paper, we study this property, and uncover its surprising and insightful behavior. Precisely, we are interested in the local complexity of parity, which is the minimum number of bits per certificate needed to certify that the graph has an even number of nodes. All our results apply to arbitrary congruence, that is, having 0 mod k nodes, but we focus on parity for simplicity. In order to have a more informed discussion, let us summarize what is known about local certification of parity.

1.1

What is known about certifying parity

It appears that (what we know about) the local complexity of certifying parity varies significantly depending on our assumptions about the graph topology. Let us discuss cycles, trees and general graphs.

In cycles In cycles, parity is equivalent to bipartiteness, which is of course not true in general graphs. Bipartiteness can easily be certified (in all graphs) by providing a 2-coloring as a certification, and this uses only 1-bit certificates. Hence, the local complexity of parity in cycles is exactly 1. Certifying that the cycle has length 0 mod k, for some constant k, is also easy: the prover only needs to encode a counter modulo k following an arbitrary orientation of the cycle, and this uses log k bits. These certifications do not require the graph to have unique identifiers, and the nodes only need to communicate with their direct neighbors. Interestingly, certifying that a cycle has an odd number of nodes (or more generally, that its length is a mod k, for fixed a = ̸ 0 and k) requires Ω(log n) bits (where n is the number of nodes) and unique identifiers, even if the nodes can communicate with neighbors at some arbitrary constant distance [15]. At an intuitive level, this difference between even and odd size can be justified in the following way. For parity, it is enough to use everywhere the same pattern of certificate, alternating 0s and 1s. Now for “non-parity”, one could try to adapt this approach by using the same alternating pattern, except on exactly one node. But certifying

1

For convenience, we define local certification for graph properties, though it can also apply to distributed data structures like spanning trees.

N. Bousquet, L. Feuilloley, J. Valenzuela, S. Zeitoun

that there exists exactly one node with a special role boils down to certifying the existence of a leader, which is known to require unique identifiers and local complexity Θ(log n).

In trees The case of trees is essential for this paper, because all our upper bounds build on the certification in trees. Suppose first that we have a rooted tree, with the edges oriented towards the root. We can certify parity in such trees with just one bit. In correct instances, every node receives as its certificate the number of nodes in its subtree (including itself) modulo 2. We will refer to these counters as parity aggregates. Parity aggregates are easy to check in directed trees: every node verifies that the sum of its children certificates, plus 1, is equal to its certificate, modulo 2. This scheme can be adapted to undirected trees as follows. On correct instances, the prover chooses an arbitrary root, gives to every node its distance to the root modulo 3, in addition to the parity aggregates. It is well-known that such counters, that we will call mod-3 counters, encode and certify a proper orientation in trees. Note that this orientation technique via mod-3 counters does not encode a proper spanning tree in general graphs. There are two main issues: (1) the counters might encode a directed graph with cycles and (2) a node might not be able to identify its parent: if it has counter c, there might be several neighbors with counter c − 1.

In general graphs While parity certification is well-understood in trees and cycles, no specific technique is known for parity in general graphs. Consequently, the state-of-the-art upper bound consists in certifying the value of n, and checking that it is even. In such a scheme, on correct instances the prover (1) certifies a spanning tree and (2) encodes at each node the size of its subtree. The nodes then (1) check the spanning tree, (2) check the subtree counters, and (3) the root checks that the value of its subtree is even. This scheme requires identifiers and uses Θ(log n) bits even for just the spanning tree part, even when allowing communication at arbitrary constant distance [15]. Regarding the lower bound, we know almost nothing: only that at least 1 bit is required. This contrasts sharply with non-parity which requires Ω(log n) [15] in a powerful model and in cycles, as mentioned earlier. Given the wide gap between the trivial 1-bit lower bound, and the “overkill” upper bound, we ask: ▶ Question 1. What is the local complexity of parity in general graphs? Is it constant, or O(log n), or in between? Do we need identifiers to achieve it?

1.2

Motivations

Let us now describe our motivations to study the local certification of parity, beyond its simplicity and the gap between upper and lower bounds.

A challenge for lower bound techniques Parity may be the simplest example of a property for which standard lower bound techniques fail. The two main lower bound techniques used in local certification are the so-called cut-and-plug and communication complexity techniques. Let us explain why the known implementations of these techniques fail, and why we believe that any sophisticated adaptation is likely to fail as well.

3

4

The local complexity of certifying parity

Cut-and-plug works by selecting accepting cycles, and using a counting argument to show that combining chunks of these cycles can create a no-instance, where the nodes incorrectly accept [18, 15]. Since this method relies on cycles, and cycles are trivial for parity, the basic version of this technique cannot be applied. While cut-and-plug has been applied to graphs more complex than cycles, e.g. in [10], these graphs remain cycle-like and the certification for cycles can easily be adapted to them. In essence, to apply the counting arguments there must be a way to easily cut and combine pieces of yes-instances, and this requirement constrains the topology in a way that makes parity easy. Communication complexity reductions typically take the following form. For every n, there exists a base graph, known to all nodes, with a fixed identifier assignment. This base graph contains two special subsets of vertices that are far apart in the graph, with a small cut between them. The lower bound instances are built by adding arbitrary edges within each subset. The intuition of the argument is then the following. In order to correctly decide the property, at least one node must know both special edge sets, which is a lot of information. Since this information can only be transferred via certificates, and the graph has a small cut, some node must have a large certificate. In such proofs, all the nodes know the base graph and thus the total number of nodes, which of course makes parity trivial.2 One can of course imagine more flexible constructions, where the base graph is not fully known. However, we argue that the communication complexity argument is fundamentally inadequate for parity. This type of proof always relies on the fact that a lot of information should go through a small cut, forcing the certificates to be large. But for parity the only information needed is whether each part has an odd or even count! This basically rules out any strategy where one would only care about communication between a few well-identified parts of the graph. Thus, extensions to multi-party complexity are equally unpromising. A coarse summary of the above is that lower bound instances that can be easily partitioned, especially via small cuts, are inadequate for proving lower bounds for parity. Another classic technique to prove lower bounds in distributed computing, one that does not require small cuts, is to use lifts or covering maps. Unfortunately, this approach also fails quickly and irreparably. Indeed, the size of a lift is always a multiple of the size of the original graph, hence the parity is preserved, and no contradiction can be derived.

Congruence predicates as a class of properties Recent work proved that in anonymous cycles, no property has local complexity both superconstant and sublogarithmic (that is, in ω(1) ∩ o(log n)) [4]. The properties that are in the O(1)-regime are basically those that can be described by a finite number of equations of the form n = 0 mod k. Thus, parity is the canonical example of a well-motivated class of properties, and our work investigates the behavior of this class, when moving from cycles to general graphs.

2

Note that in general the a priori knowledge of the base graph is a strength and not a weakness of the technique, since it allows to derive lower bounds in a more powerful model. For parity it is simply too strong to be useful.

N. Bousquet, L. Feuilloley, J. Valenzuela, S. Zeitoun

A natural extension of the metatheorem line of research There is an ongoing effort to understand the local complexity of first-order (FO) and monadic second-order (MSO) formulas. These formulas capture locality in a logical framework, rather than relying on the bounded verification radius typically used in locally checkable labelings. See [2] for a discussion of this approach. Such properties can have a large local complexity in general graphs. For example, non3-colorability is a simple FO formula that has complexity Ω(n2 / log n) (almost matching the O(n2 ) upper bound that holds for any property). The main idea of the current line of research is that these properties become tractable in more structured graphs. Theorems establishing upper bounds for specific logics and structured graphs are called meta-theorems, and a series of such theorems have emerged in recent years [9, 1, 13, 14, 7, 2]. These theorems provide certifications of size O(log n) for all FO or all MSO formulas on graphs of bounded treedepth/pathwidth/treewidth/cliquewidth/expansion. Counting modulo a constant is a typical example of a property that cannot be expressed in (plain) FO or MSO. In that sense, studying parity and similar properties complements the study of these logics. We will see that the meta-theorem approach also inspired us to study structured graphs.

1.3

Results and techniques

Let us now state our three main results and briefly sketch their proofs.

Upper bound in general graphs First, we prove that parity can be certified with a constant number of bits, in a sufficiently powerful model of certification. ▶ Theorem (Informal version of Theorem 3 in Section 3). In general graphs equipped with identifiers, and verification radius 2, parity can be certified with 3 bits. The technical challenge for proving this theorem is that the only approach we know for certifying parity (beyond cycles) is to aggregate counters along the edges of a spanning tree, and a spanning tree requires Ω(log n) bits to be encoded. Intuitively, when encoding a spanning tree locally, we need to allow every node to identify its parent and children. Using identifiers explicitly is of course too expensive, if we aim for constant complexity. One approach is to encode new identifiers that are only locally unique, but this is not better in graphs that have linear maximum degree. Another approach is to use the local structure of the graph to distinguish between nodes, but this does not work in highly symmetric graphs. We make several observations that allow us to bypass this obstacle. We do not need the prover to be able to encode an adversarially chosen spanning tree, any spanning tree is fine. The nodes can distinguish (some of) their neighbors, even without certificates: for example, their neighbor with the smallest ID. Using mod-3 counters from a chosen root, we can guide the direction in which the nodes should find their parent. Combining these observations, we design the following strategy for the prover: 1. Choose an arbitrary root. 2. Provide every node with its distance to the root modulo 3.

5

6

The local complexity of certifying parity

3. Compute the spanning tree formed by every node choosing among its neighbors closer to the root the one with the smallest ID. 4. Provide every node with the size of its subtree in this spanning tree, modulo 2. Two challenges arise. First, by communicating with its direct neighbors, a node can easily identify which node is its parent, but not which nodes are its children. This is why we need a verification radius of 2: every node v can then check whether each of its neighbors has chosen v as its parent. Given this, every node can check that the parity is aggregated correctly, as in the tree case. The second challenge is to make the scheme robust against an adversarial prover in no-instances. A blatant weakness of the strategy above is that we cannot guarantee that the parent relation, defined by the mod-3 counter and smallest-ID, is indeed acyclic. For example, in a cycle of size n = 3k, the prover can assign labels 1, 2, 3, 1, 2, 3... and pretend that these are mod-3 counters. In this case, the identifiers are irrelevant for the verification, and no node detects a cycle in the parent relation. The pointers should then be considered as pointers to successors, and not as pointers to parents. In general, the successor relation globally defines a collection pseudo-trees: cycles with trees attached to them. Surprisingly, we can prove that this does not compromise the correctness of the scheme! Indeed, we can prove that if all nodes accept with our scheme, then the pointers must form a collection of pseudo-trees of even size, implying that the graph is a correct instance. We now make a few observations about the theorem and the proof. First, even though the proof is involved, the scheme itself is very simple and highly efficient in terms of certificate size: it only needs two bits for the mod-3 counters, and one bit for the parity aggregates. Second, while the identifiers are required, the certificates only depend on the identifier assignment in an order-invariant way: if another ID assignment with the same global order were used, the same certificate assignment would still work. As far as we know, this is the first example of an order-invariant local certification. In the literature, either the certificates do not depend on the IDs (e.g. for certifying k-colorability) or they rely on the actual value, such as when naming a leader in the graph.

Lower bound in general graphs We now investigate whether the identifiers and verification radius 2 are necessary to achieve constant local complexity. We present the following lower bound. ▶ Theorem (Informal version of Theorem 14 in Section 5). In anonymous graphs, with verification radius 1, the local complexity of parity is in Ω(log log∗ n). As previously discussed, the standard lower bound techniques fail for parity. At a high level, we bypass the obstacles of these techniques by: (1) using more complex graph structures, (2) aiming at changing node degrees without causing rejection, and (3) replacing the classic counting argument by a higher-order Ramsey-type theorem. The general strategy is simple. We begin with a family of graphs, each with an even number of nodes. We show that, for any possible scheme using short certificates, and for any graph G of this family, there exist two nodes a and b, that have the following property. If we take two copies of G and identify the vertex a from the first copy with the vertex b from the second copy, all the vertices accept the resulting graph. This is a contradiction, because the new graph has 2|G| − 1 nodes, which is odd. We emphasize that in this reasoning we combine two instances by identifying vertices, rather than by rerouting edges as is usually done.

N. Bousquet, L. Feuilloley, J. Valenzuela, S. Zeitoun

The graph family we use consists of “powerset graphs”. A graph G in this family is a bipartite graph G = (V1 ∪ V2 , E), where V1 has m nodes (with m odd), and V2 has 2m − 1 nodes. For every non-empty subset of V1 , there exists exactly one node of V2 that is linked to exactly this subset. See Figure 1. V1

V2

Figure 1 A graph G from our lower bound instance family. Here m = 3, 2m − 1 = 7 and n = 10.

We use the finite unions theorem [16, Chapter 3], a powerful tool from Ramsey theory about colorings of set families, to prove the following. In our lower bound graphs, for any certificate assignment using o(log log∗ n) bits per node, there exist three nodes a, b and c in V2 , such that: (1) they are given the same certificate, and (2) they are adjacent to sets A, B and C respectively, such that A ∩ B = ∅ and C = A ∪ B.3 Now, as announced, we take two copies of G, with the same accepting certificate assignment, and identify vertex a from the first copy with vertex b from the second copy. This certificate assignment is well-defined because a and b have the same certificate. It is also accepting: all the nodes have the same view as in G, except the merged vertex, which has exactly the same view as vertex c in G, and therefore also accepts. Note that for this part of the argument to hold, we crucially need the verification radius to be one, and the network to be anonymous.

Upper bound in structured sparse graphs Our lower bound graphs have complex structures, in the sense that many standard parameters are unbounded in this graph family, for example the maximum degree, the treewidth and even the VC dimension. We investigate whether this is an artifact of our proof, or whether it is unavoidable. A concrete question is: Can we still get super-constant lower bounds if we bound some parameters or restrict to well-known graph classes, such as planar graphs? We show that this complexity is necessary, by proving an upper bound in a very general family of structured graphs. ▶ Theorem (Informal version of Theorem 7 in Section 4). In any family of anonymous graphs of bounded expansion, parity has constant local complexity, even with verification radius 1. Bounded expansion basically ensures that a graph class is structurally sparse. In contrast, the standard notion of sparsity is coarse, as it only requires a global condition: a bounded ratio of edges to vertices. Under this definition, even dense graphs can be made sparse by simply attaching a sufficiently long path, or subdividing their edges. In many cases, this basic definition of sparsity is not demanding enough to be useful, and bounded expansion is an essential alternative. Intuitively, a family of graphs has bounded expansion if it is sparse

3

We can avoid using the finite union theorem, by relying on more standard Ramsey theorems and additive combinatorics results, but this only yields an ω(1) bound rather than Ω(log log∗ n).

7

8

The local complexity of certifying parity

and cannot be made arbitrarily dense by contracting small subgraphs. A bit more formally, a family of graphs has bounded expansion if, for any t, the density remains bounded by some function f (t), after contracting subgraphs of radius at most t and deleting vertices. See Section 4 for proper definitions. Bounded expansion graphs encompass many standard graph classes such as bounded degree graphs, random graphs of bounded average degree (with high probability), bounded treewidth graphs, planar graphs, and more generally minor-free graphs. These classes have proven interesting from a local certification perspective: for example, there exists constantsize certifications for perfect matchings in planar graphs [5] and leader election in grids [11, 6]. A recent breakthrough establishes an efficient meta-theorem in bounded expansion graphs in the CONGEST model, and the same tools enable local certification of all FO formulas with local complexity O(log n) [2]. This result is incomparable with ours, since we use constant-size certificates and parity is not in FO. Nevertheless it highlights that this structural notion of sparsity is central for local certification, and distributed graph algorithms in general. We turn to our proof techniques. We build on the ideas behind the scheme for general graphs. Recall that our upper bound relied on two key assumptions: unique identifiers (to identify a successor) and verification radius 2 (to identify the predecessor/children). We prove that we can leverage the structure of bounded expansion graph classes to certify parity without these assumptions. The main tool is conflict-free colorings. These are colorings of the nodes of the graph, such that for every node, some color is used exactly once in its neighborhood. That is, for every node v, there exists a neighbor w with some color c, such that no other neighbor of v has color c. It was proved recently that for bounded expansion graph classes we can get conflict-free colorings with a constant number of colors [17]. The basic idea is as follows: the prover computes a conflict-free coloring of the graph, and provides each node with its color, and the color of its successor. This is unambiguous because there is a unique node with this color in the neighborhood. This alone is insufficient to ensure correct parity aggregates, but we can enhance it by using mod-3 counters, and a collection of conflict-free colorings taking the mod-3 layers into account. The proof then follows the general case: we prove that a graph is accepted if and only if it has a spanning collection of even pseudo-trees, which is equivalent to parity. Although conflict-free colorings have been extensively studied in graph theory, we are unaware of any prior application in distributed computing.

1.4

Discussions

A surprising discrepancy in the complexities Our first two theorems show that in two rather close models of local certification the local complexity can be different. We consider the two models to be close because they follow the standard framework, unlike more recent generalizations using multiple provers or a non-constant number communication rounds. We now elaborate on why this discrepancy is surprising. We now describe how the local complexity depends on the verification radius and the identifier model in previous work. Regarding the verification radius, two behaviors have been identified. 1. For most classic properties, increasing the verification radius from 1 to an arbitrary constant only decreases the certificate size by a constant factor. This phenomenon was

N. Bousquet, L. Feuilloley, J. Valenzuela, S. Zeitoun

studied in [15] by introducing locally checkable proofs, as a generalization of the original model of proof-labeling schemes [18].4 2. For some properties, increasing the verification radius eventually makes certification trivial, and this threshold can be deduced directly from the definition of the property. For example, certifying that a graph is triangle-free requires near-linear certificates at distance 1, but is trivial at distance 2. See [3] for a detailed study of such problems. We also observe a dichotomy for the role of the identifiers. 1. Most classic properties, such as leader election or clique detection, cannot be solved without identifiers for any constant verification radius. 2. For some properties, the natural certification does not use identifiers, for example kcolorability. With parity, we encounter in a new situation: a change of verification radius and identifier model alters the local complexity, for no obvious reason. Indeed, it is not clear why parity exhibits a fundamental difference between radius 1 and radius 2, and why identifiers would be required, given that the problem does not rely on a node having a specific role.

The problems we leave open Since our first two theorems differ in both the verification radius and the identifier model, a natural question arises: what about the intermediate models? ▶ Open problem 1. Is it possible to certify parity with constant local complexity, in anonymous graphs with verification radius 2, or in identified graphs with verification radius 1? We note that the simplest adaptations of our techniques do not work: subdividing edges in the lower bound breaks the constructions, and replacing IDs with pseudo-IDs is challenging without assumptions on the structure of the graph. Even within the models of this paper, large gaps in our understanding persist. The local complexity in the anonymous case with radius 1 remains wide open. An upper bound in this setting can be obtained by using a conflict-free coloring (as in our third contribution), but this requires O(log n) bits in general graphs, as up to n colors are needed. Since our lower bound is just above constant, the gap remains very large. ▶ Open problem 2. What is the local complexity of parity in anonymous graphs with verification radius 1? It is possible that an Ω(log n) lower bound can be achieved, but this would require fundamentally new ideas. Indeed, in our lower bound, we crucially need some nodes of different degree to be assigned the same certificate, and this cannot be guaranteed in our lower bound instances if the certificates have size Ω(log log n). This is because the nodes that are on the side V2 (where there is one node for every subset of side V1 ) have degree m = O(log n), and writing the degree of each such node in its certificate only takes O(log log n) bits.

4

It is conjectured that the certificate size always decreases at least linearly with the verification radius. This known as the trade-off conjecture, raised several times in the literature, and a slightly weaker version proved very recently [12].

9

10

The local complexity of certifying parity

On the power of constant-size local certification Let us now shift our focus slightly and discuss the power of constant-size certification in anonymous graphs with verification radius 1. It is known that the languages of paths (with inputs) that have constant local complexity in this setting are exactly the regular languages [4]. And since counting modulo a constant is straightforward for a finite automaton, our lower bound implies that when moving from paths to general graphs, we lose the ability to count. We wonder whether the properties with constant local complexity in general graphs correspond to restrictions of regular languages. For example, we could explore analogues of locally testable languages (regular languages defined by forbidden subwords), or star-free (regular languages that can be expressed without Kleene star). However this approach is challenging: the typical example of a property of local complexity is 3-colorability, and 3-colorable graphs can have highly complex structures. ▶ Open problem 3. Can we characterize the properties that have constant local complexity without referring to local certification? In general graphs, or even in specific graph classes?

Similarities with LCL theory Finally, readers familiar with the theory of locally checkable labelings will recognize similarities between some concepts of this paper and the O(log∗ n) regime of complexity in LOCAL. First, for the upper bound in general graphs we use a scheme that is order-invariant, which is reminiscent of Naor-Stockmeyer result [19] which shows that any constant-time algorithm in the LOCAL model can be made order-invariant. Second, the log∗ n complexity of our lower bound is the same as the complexity of symmetry breaking (e.g. 3-coloring a cycle). We do not know whether a deep connection exists between these two branches of distributed computing, but we highlight that the graphs used for the lower bound do not have bounded degree, which implies that easy adaptations are not expected.

1.5

Organization of the paper

The rest of the paper is organized as follows. In Section 2, we provide the formal definitions of the models used in the paper. In Section 3 and 4, we state and prove our upper bounds for general graphs and bounded expansion graph classes, respectively. In Section 5, we state and prove our lower bound. Note that the order of the sections differs from the order in which discussed the results in the introduction.

2

Model and definitions

Graph notions All the graphs we consider in this paper are simple, loopless, finite, undirected, and connected. If G is a graph, we denote by V (G) and E(G) its sets of vertices and edges respectively; we also use V and E when G is clear from the context. We denote by n the number of vertices.

Models of local certification. Let G = (V, E) be an n-vertex graph, and c > 0. An identifier assignment of G in the range [nc ] is an injective function ID : V (G) → [nc ]. If G is equipped with an identifier assignment, we say that we are in the locally checkable proof model (or LCP model for short),

N. Bousquet, L. Feuilloley, J. Valenzuela, S. Zeitoun

else we say that we are in the anonymous model. Finally, let C be a non-empty set, called the set of certificates. A certificate assignment of G with certificates in C is a mapping c : V → C.

Local view and verification algorithm Let G = (V, E) be a graph, r ⩾ 1, and c be a certificate assignment for G. Let u ∈ V . The local view of u at distance r consists in all the information available at distance at most r from u in G, that is: its own certificate and its own identifier (if any); all the vertices at distance at most r from u, and all the edges having at least one endpoint at distance at most r − 1 from u; the restriction of the certificate assignment c and of the identifier assignment (if any) to these vertices. A verification algorithm (or verification procedure) is a function taking as input the local view at distance r of a vertex, and outputting a decision, accept or reject. The integer r is called the verification radius of the algorithm. If the verification radius is equal to r, we also say that we are in the r-local model.

Certification scheme Let C be a class of graphs and P be a property on graphs in C. Let s : N → N. We say that there exists a certification scheme for P with local complexity s if there exists a verification algorithm such that the two following conditions are satisfied: Completeness: For every n-vertex graph G ∈ C that satisfies P, and for every identifier assignment of G (if we are in the locally checkable proof model), there exists a certificate assignment in [2s(n) ] such that the verification of every vertex accepts (we say that the graph is globally accepted). Soundness: For every graph G ∈ C that does not satisfy P, for every identifier assignment of G (if we are in the locally checkable proof model), for every k ∈ N and every certificate assignment in {0, . . . , 2k − 1}, at least one vertex rejects. We often say that the certificates are assigned by an external prover. Let us emphasize that, if G does not satisfy P, then for any assignment of certificates of any size, at least one vertex rejects. Let us also point out the fact that in a certification scheme for a property P in some class C, the vertices have the promise that the graph belongs to C. In other words, the certification scheme depends on the property P and on the class C, and we are not concerned by the output of the verification procedure of the vertices in graphs that do not belong to C.

Computational power of the prover and vertices Note that, in the previous definitions, there is no limitation on the computational power of the prover and the vertices. Namely, the verification of the vertices is a just a function, with no more requirements (in particular, it is not necessarily computable in polynomial time, or even decidable). This definition only makes stronger the lower bounds on the local complexity, by showing that they do not come from computational limits. However, when designing certification schemes in practice, it will often turn out to be computable in polynomial time.

11

12

The local complexity of certifying parity

Discussion on the models In general, it is easier to certify a property in the locally checkable proof model than in the anonymous model. Indeed, proving an upper bound on the local complexity of some property in the anonymous model also proves it in the LCP model, simply because a certification scheme in the anonymous model also works in the LCP model. Similarly, a lower bound in the LCP model automatically gives a lower bound in the anonymous model.

3

Upper bound in general graphs

In this section, we establish the constant local complexity of (generalizations of) parity in the model with verification radius 2 and identifiers. Let us start by a couple of definitions, and then state and prove our theorem. ▶ Definition 1. The underlying graph of an oriented graph G is the non-oriented graph obtained from G by forgetting the orientation of the edges. ▶ Definition 2. An oriented cycle is an oriented graph whose underlying graph is a cycle, and such that each vertex has exactly one incoming and one outgoing edge. ▶ Theorem 3. Let k ⩾ 2, and let P be the property of having a number of vertices divisible by k. In the 2-local LCP model, the local complexity of P is O(log k). Proof. Let us describe a 2-local certification scheme for P, in the locally checkable proof model. Let G be a graph. Let us first describe how the prover assigns the certificates on a correct instance. First, it chooses an arbitrary vertex r ∈ V (G), and computes the following spanning tree T rooted at r: for every vertex u = ̸ r at distance d from r, its parent in T is its neighbor at distance d − 1 with minimum identifier. Note that this defines indeed a spanning tree (because T is a particular breadth-first-search tree). Finally, the prover writes, in the certificate of each vertex u, the following information (which can be encoded on O(log k) bits): (C1) the distance du from u to r modulo 3; (C2) the number of vertices nu in the subtree of T rooted at u modulo k. Let us now describe the verification procedure of the vertices. Consider a certificate assignment c to the vertices (that is, some assignment of values du and nu ). If the set {v ∈ N (u) | dv = du − 1 mod 3} is empty, we say that u is a root (with respect to the certificate assignment c). If this set is non-empty, we define the parent of u (again, with respect to the certificate assignment c) as the vertex with minimum identifier in this set. If v is the parent of u, we also say that u is a child of v. If u has no child, we say that it is a leaf. Note that, since each vertex u has a view at distance 2, it can determine, for every neighbor v, if it is itself the parent of v (because it sees the certificates and identifiers of the neighbors of v). Thus, it can determine its set of children. The verification of every vertex u consists in the following, by rejecting if at least one condition is not satisfied, and accepting if both conditions are satisfied: P (V1) u checks that nu = 1 + v∈S nv mod k, where S denotes its set of children; (V2) if u is a root, it checks that nu = 0 mod k. The completeness of this scheme is straightforward: indeed, if the number of vertices in G is divisible by k, and if the prover assigns the certificates as described in 1 and 2, no vertex will reject in its verification procedure.

N. Bousquet, L. Feuilloley, J. Valenzuela, S. Zeitoun

Let us prove the soundness of this scheme. Let c be a certificate assignment such that no vertex rejects, and let us prove that G satisfies P. In fact, we will not prove that the parent relationship with respect to c defines a correct spanning tree, because it might not be the case. However, even if this parent relationship does not define a correct spanning tree, we will still be able to prove that the property P holds. Let us consider the following → − oriented graph G , on the same set of vertices as G. For every edge {u, v} of G, we put the → − → − edge u → v in G if and only if v is the parent of u with respect to c. Note that, in G , each vertex has at most one outgoing edge, and it does have one if and only if it is not a root. Let → − us consider a connected component C of the underlying graph of G . Let us denote by |C| → − its number of vertices. We aim to prove that |C| is divisible by k. Since each vertex of G → − has at most one outgoing edge, then C has at most |C| edges in G . Moreover, since C is → − connected in the underlying graph of G , it has at least |C| − 1 edges. We say that C is a type-1 component if it has |C| − 1 edges, and a type-2 component if it has |C| edges (see Figure 2 for an illustration). We now treat these two cases separately.

− → − → Figure 2 Left: a type-1 component in G . Right: a type-2 component in G .

First, assume that C is a type-1 component. Since it has |C| − 1 edges, it has a unique root, and its underlying graph is a tree. Thus, C is a rooted tree. Let us denote its root by r. Since no vertex rejects in 1, for all vertex u which is a leaf, we have nu = 1. Then, by an immediate induction, we obtain that for every vertex u in C, nu is equal to the number of vertices in the subtree of C rooted at u modulo k (again because u does not reject in 1). In particular, we have nr = |C| mod k. Finally, since r does not reject in 2, we have nr = 0 mod k, so |C| is divisible by k. Now, assume that C is a type-2 component. Since it has |C| edges, its underlying graph is a tree plus an edge. In other words, it is a cycle plus some trees attached to the vertices of → − this cycle. Let us denote this cycle by C0 . Since every vertex in G has at most one outgoing → − neighbor, then C0 is an oriented cycle in G . Let us denote by s the number of vertices in C0 , and by u1 , . . . , us its consecutive vertices. For every i ∈ {1, . . . , s}, let us denote by Ti the tree attached to ui (including ui itself), and by ti its number of vertices. The tree Ti is a rooted tree, and its root is ui (because the outgoing neighbor of ui is in C0 , so ui does Ps not have any outgoing neighbor in Ti ). Also, we have |C| = i=1 ti . See Figure 3 for an illustration. Let i ∈ {1, . . . , s}. Since no vertex rejects in 1, for every vertex u of Ti which is a leaf, we have nu = 1. By an immediate induction, for every vertex u in Ti different from ui , nu is equal to the number of vertices in the subtree of Ti rooted at u modulo k. Since ui has also ui−1 mod s as a child, we get nui = ti + nui−1 mod k (if i > 1) and nu1 = t1 + nus mod k. We thus obtain the following equalities.

13

14

The local complexity of certifying parity

T1 u2

C C0

u3

u1

u4 u5

u6

Figure 3 A type-2 component C. The dashed areas are the oriented cycle C0 and the rooted tree T1 (rooted at u1 ). Here, we have t1 = 9, t2 = 2, t3 = 4, t4 = 3, t5 = 1 and t6 = 3.

nus = ts + nus−1 mod k = ts + ts−1 + nus−2 mod k = ... s X = ti + nu1 mod k i=2

=

s X

ti + nus mod k

i=1

Ps Thus, i=1 ti = 0 mod k, so |C| is divisible by k. To conclude the proof, we proved → − that, for every connected component C of the underlying graph of G , |C| is divisible by k. → − → − Then |V ( G )| is also divisible by k. Finally, since G and G have the same number of vertices, we get that |V (G)| is divisible by k. So G satisfies P, which proves the soundness of the scheme. ◀

4

Upper bound in bounded degree and bounded expansion graphs

In the previous section, we proved that for every k ⩾ 1, the property P of having a number of vertices divisible by k is a local property in the 2-local LCP model. Since this model is not the weakest possible, a natural question is whether the unique identifiers, and the verification radius equal to 2, are necessary or not for P to be local. In Section 5, we partially answer this question, by showing that at least one of these two assumptions is necessary. More precisely, we prove that, in the 1-local anonymous model, P is not local anymore (see Theorem 11). However, an important remark is that, if there exists a spanning tree T such that the prover can encode the parent of each vertex in the certificates, and if each vertex can recover its parent and its set of children thanks to the certificates, then, with only O(log k) additional bits (corresponding to nu mod k in the proof of Theorem 3), the vertices can verify the property P, by proceeding exactly as in the proof of Theorem 3. In the 2-local LCP model, to do so, it was sufficient for the prover to write the distance to the root du mod 3 in the certificate of each vertex u (then, the vertices used the identifiers and the verification radius 2 to recover their parent and children). In the 1-local anonymous model, even if the

N. Bousquet, L. Feuilloley, J. Valenzuela, S. Zeitoun

same strategy does not work anymore, we can wonder if it is possible to encode this parent relationship using certificates of constant size, in restricted graph classes. The first example of a graph class in which such a constant-size encoding is possible in the 1-local anonymous model is in bounded-degree graphs. In graphs of maximum degree at most ∆, the prover can compute a proper distance-2 coloring (that is, a coloring of the vertices such that every vertices at distance at most 2 have different colors), using ∆2 + 1 colors. Then, with O(log ∆) bits, it encodes, in the certificate of every vertex, its color. The vertices can check that this distance-2 coloring is indeed proper. Finally, for every vertex u, all its neighbors have distinct colors, so the prover can encode its parent v simply by writing the color of v in the certificate of u, using again O(log ∆) bits. We formalize this in the following theorem. ▶ Proposition 4. Let k ⩾ 2, and let P be the property of having a number of vertices divisible by k. In graphs of maximum degree ∆, in the 1-local anonymous model, the local complexity of P is O(log k + log ∆). Proof. Let G be a graph of maximum degree ∆. Then, G has a proper distance-2 coloring (that is, a coloring of the vertices such that every vertices at distance at most 2 have distinct colors) using at most ∆2 + 1 colors. The prover chooses a spanning tree T of G and a proper distance-2 coloring φ of G. It writes, in the certificate of each vertex u, the following information (which can be encoded on O(log k + log ∆) bits): (C1) the color φ(u) of u; (C2) the color φ(v) of the parent v of u in T (except if u is the root of T ); (C3) the number of vertices nu in the subtree of T rooted at u modulo k. The verification procedure of the vertices is the following. Let c be a certificate assignment. First, every vertex u checks that the colors written in 1 in its certificate and in the certificates of its neighbors are all distinct. Then, we say that u is a root if the color of its parent is not written in 2. If u is not a root with respect to c, it checks that it has a unique neighbor, its parent, colored with the color written in 2. The children of u are its neighbors v such that u is the parent of v. Finally, u is a leaf if it does not have any children. Every vertex u can determine its set of children, which are its neighbors v such that the color of u is written in 2 in the certificate of v. The vertices verify that items 1 and 2 of the proof of Theorem 3 both hold. All the rest of the proof (the completeness and soundness of the scheme) is identical as in Theorem 3. ◀ We now generalize Proposition 4 to the larger class of graphs of bounded expansion. Again, the idea is to find a spanning tree T such that encoding the parent relationship in T can be done with a constant number of bits. But first, let us define the class of graphs of bounded expansion. ▶ Definition 5. Let G, G′ be two graphs. We say that G′ is a minor of G if there exists a (non-necessarily induced) subgraph H of G, and a partition of the vertices of H into connected sets, such that G′ is the graph obtained from H by contracting these sets into single vertices. If each of these sets has diameter at most t, we say that G′ is a t-shallow minor of G. ▶ Definition 6. A class of graphs C has bounded expansion if there is a function f such that, for each t ⩾ 1, each G ∈ C and each t-shallow minor G′ of G, we have |E(G′ )|/|V (G′ )| ⩽ f (t). Now, we aim to prove the following result:

15

16

The local complexity of certifying parity

▶ Theorem 7. Let C be a class of graphs of bounded expansion. Let k ⩾ 2, and let P be the property of having a number of vertices divisible by k. In C, in the 1-local anonymous model, the local complexity of P is O(log k + g(C)), where g(C) is a constant that depends only on the class C. The proof of Theorem 7 relies on the notion of conflict-free coloring, that we define now. ▶ Definition 8. A conflict-free coloring of a graph G is a coloring φ of V (G) such that, for every u ∈ V (G), there exists v ∈ N (u) such that v is the only vertex in N (u) colored with φ(v). The conflict-free coloring number of G, denoted by χcf (G), is the smallest integer c such that G has a conflict-free coloring with c colors. We will rely on the following result by Hickingbotham [17], which states that a class of bounded expansion has bounded conflict-free coloring number. ▶ Theorem 9 ([17]). Let C be a class of graphs of bounded expansion. Then, there exists a constant f (C) depending only on the class C, such that, for every G ∈ C, we have χcf (G) ⩽ f (C). ▶ Remark 10. If C is a class of graphs of bounded expansion, it is immediate from the definition that the class obtained from C by taking all the subgraphs of graphs in C has also bounded expansion. Thus, the result of Theorem 9 remains true for all subgraphs of graphs in C. We are now able to prove Theorem 7. Proof of Theorem 7. Let G ∈ C. Let us first describe how the prover assigns the certificates on a correct instance. First, it chooses an arbitrary vertex r ∈ V (G). Let δr be the maximum distance from r to any vertex in G, and, for every integer 1 ⩽ d ⩽ δr , let Gd be the bipartite graph obtained from G by keeping only the vertices at distance d − 1 and d from r, and the edges between these two sets of vertices (we do not keep the edges between two vertices at distance d − 1, and between two vertices at distance d). By Theorem 9 and Remark 10, Gd has a conflict-free coloring using f (C) colors, where f (C) depends only on C. The prover computes, for every d ∈ {1, . . . , δr }, such a conflict-free coloring φd of Gd . Finally, the prover computes the following spanning tree T of G, rooted at r. For every vertex u = ̸ r at distance d from r, the parent of u in T is an arbitrary neighbor v at distance d − 1 from r, such that v is the only neighbor of u at distance d − 1 from r colored, in the coloring φd , with the color φd (v). Since φd is a conflict-free coloring of Gd , such a vertex v exists. Finally, for every u ∈ V (G), the prover writes in the certificate of u the following information: (C1) the distance du from u to r modulo 3; (C2) the number of vertices nu in the subtree of T rooted at u modulo k; (C3) if u ̸= r, the color φdu (v) of the parent v of u in T in the coloring φdu ; (C4) if du < δr , the color φdu +1 (u) of u in the coloring φdu +1 . Given a certificate assignment c, we say that a vertex u is a root (with respect to the certificate assignment c) if the set {v ∈ N (u) | dv = du − 1 mod 3} is empty (where du , dv are the integers written in 1 in the certificates of u and v). Each vertex u performs the following verification procedure: (V1) if u is not a root, it checks that it has a unique neighbor v such that dv = du − 1 mod 3 and the color written in 3 in the certificate of u is the same as the color written in 4 in the certificate of v.

N. Bousquet, L. Feuilloley, J. Valenzuela, S. Zeitoun

17

If no vertex rejects in 1, every non-root vertex u with respect to c has a unique neighbor v satisfying the condition in 1. This neighbor is called its parent (with respect to c). If v is the parent of u, we say that u is a child of v. If u has no child, we say that it is a leaf. Note that each vertex u can determine its set of children. Indeed, the children of u are its neighbors w such that the color of w written in 3 in the certificate of w is the same as the color of u written in 4 in the certificate of u. The verification of u then continues with the two following steps: (V2) if u is a root, it checks that nu = 0 mod k; P (V3) in all cases, u checks that nu = v∈S nv mod k, where S denotes its set of children. The proof of the correctness of the scheme is identical as in the proof of Theorem 3.

5

◀

Lower bound

We now move on to our lower bound. ▶ Theorem 11. In the 1-local anonymous model, the local complexity of having an even number of vertices is ω(1). To prove Theorem 11, we will need the following result from Ramsey theory, called the Folkman-Rado-Sanders Finite Unions Theorem. The classic proof can be found in [16, Chapter 3]. ▶ Theorem 12 (Finite Unions Theorem). For every integers k, c, there exists an integer m = f (k, c) such that, if all the non-empty subsets of [m] are colored with c colors, then there exists k pairwise disjoint non-empty subsets S1 , . . . , Sk ⊆ [n] such that {∪i∈I Si | ∅ ⊊ I ⊆ [k]} (in other words, all non-empty unions of these sets) are colored with the same color. We are in particular interested with the case k = 2 in Theorem 12, which guarantees the existence of two disjoint non-empty subsets A, B ⊆ [m] such that A, B and A ∪ B have the same color, where m := f (2, c). Using this result, we are able to prove Theorem 11 Proof of Theorem 11. By contradiction, assume that it is possible to certify that a graph has an even number of vertices, in the 1-local anonymous model, with certificates of constant size s. Let c := 2s be the number of possible different certificates in such a certification scheme. Let m ⩾ f (2, c) be an odd integer, where f is the function provided by Theorem 12, and finally let n := m + 2m − 1. Note that n is even. Consider the n-vertex bipartite graph Gm , where the vertices of Gm are partitioned into two sets X, Y (to simplify the notations, we do not index X and Y by m). Let X := [m] and Y be the set of non-empty subsets of [m]. For every x ∈ X and y ∈ Y , there is an edge between x and y in Gm if and only if x ∈ y. Since Gm has an even number of vertices, there exists a certificate assignment to its vertices such that each vertex accepts. Consider such a certificate assignment, with certificates in [c]. Consider the following coloring of the non-empty subsets of [m]. Let ∅ ⊆ S ⊆ [m]. S is also a non-empty subset of vertices of X. By construction of Gm , there is a unique vertex y ∈ Y such the neighbors of y in X are exactly the vertices in S. We define the color of S as being the certificate of y. By Theorem 12, there exist two disjoint non-empty subsets A, B ⊆ [m] such that A, B, and A ∪ B all have the same color. In other words, there exist three vertices yA , yB , yA∪B ∈ Y such that: yA , yB , yA∪B all have the same certificate, and

18

The local complexity of certifying parity

A

X

B

Gm yA

Y

yB

yA ∪ B

B

A

G′m

B

A

Figure 4 The graphs Gm and G′m . In Gm , the only vertices of X which are represented are vertices in A ∪ B, and the only vertices of Y which are represented are yA , yB , yA∪B (and similarly in G′m ). The vertices yA , yB , yA∪B have the same certificates. The graph G′m is obtained by taking two copies of Gm (each one represented in one of the colored areas), and identifying yA in the first copy with yB in the second one. The corresponding vertex is the one drawn in bold. Each vertex accepts in G′m because it has the same view as a vertex which accepts in Gm .

the neighbors of yA (resp of yB , yA∪B ) in X are the vertices in A (resp in B, A ∪ B). We construct the following graph G′m , together with a certificate assignment such that every vertex accepts. We take two copies of Gm , each one equipped with the accepting certificate assignment of Gm . Then, we identify the two vertices corresponding to yA in the first copy, and to yB in the second copy. The graph resulting from this operation is G′m . Note that this operation is compatible with the certificate assignment because yA and yB have the same certificates. Moreover, G′m has 2n − 1 vertices, so it has an odd number of vertices. Finally, every vertex accepts in G′m , because the vertex obtained by identifying the vertices yA and yB in the two copies has the same view as yA∪B in Gm , and all the other vertices have the same view as they already have in Gm . This is a contradiction and concludes the proof. See Figure 4 for an illustration. ◀ Now, one can wonder if it is possible to obtain a more precise lower bound in Theorem 11. To do so, with this proof technique, we would need to obtain an upper bound on f (2, c) in Theorem 12. Such an upper bound is proven in [20, Chapter 6]. More precisely, a general upper bound on f (k, c) is proven, and the particular case for k = 2 is the following. ▶ Theorem 13 ([20]). The following inequality holds: 3c

..

.

3

f (2, c) ⩽ c where c3

c

.

..

3

is a tower of exponential of height 2c.

Using Theorem 13, we are able to get a more precise lower bound on the local complexity of having an even number of vertices. For every integers k, ℓ ⩾ 1, let tow(ℓ, k) := ℓℓ

..

.

ℓ

,

N. Bousquet, L. Feuilloley, J. Valenzuela, S. Zeitoun

19

ℓ

where the exponential tower has size k (for instance, tow(ℓ, 3) = ℓℓ ). Recall that for every integer n ⩾ 2, the iterated logarithm of n, denoted by log∗ (n), is the smallest integer k ⩾ 1 such that tow(2, k) ⩾ n. In other words, it is the smallest number of times we have to apply the (base-2) logarithm to the integer n to get a value below 1. We will prove the following lower bound. ▶ Theorem 14. In the 1-local anonymous model, for n-vertex graphs, at least Ω(log∗ (n)) different certificates are necessary to certify that the number of vertices is even. Thus, in this model, the local complexity of this property is Ω(log(log∗ (n))). To prove Theorem 14, we will use the bound of Theorem 13. Since the tower of exponential appearing in this bound does not have a constant exponent, we will need to prove first a technical result. Let denote by dlog∗ (n) (the diagonal iterated logarithm of n) the smallest integer k ⩾ 1 such that tow(k, k) ⩾ n. Before proving Theorem 14, let us prove the following lemma, that gives a comparison between log∗ and dlog∗ . ▶ Lemma 15. We have dlog∗ (n) = Θ(log∗ (n)). Proof. Since we trivially have dlog∗ (n) = O(log∗ (n)) from the definition, we just need to show that log∗ (n) = O(dlog∗ (n)). Let m ⩾ 4. For every k ∈ N, let log(k) (m) := log log . . . log m, where the logarithm is in base 2, and is iterated k times (of course, if it exists). Note that, for every integers 1 ⩽ k ⩽ m, log(k) (tow(m, m)) exists. By induction on k ∈ [m − 1], let us prove the following inequality: log(k) (tow(m, m)) ⩽ 2tow(m, m − k) log m The result is straightforward for k = 1, since log tow(m, m) = tow(m, m − 1) log m. Let k ∈ {2, . . . , m − 1}, and assume that the result holds for k − 1. In other words, assume that: log(k−1) (tow(m, m)) ⩽ 2tow(m, m − k + 1) log m By taking the logarithm of this expression, we get: log(k) (tow(m, m)) ⩽ 1 + log log m + tow(m, m − k) log m ⩽ 2tow(m, m − k) log m This proves the induction. In particular, by taking the logarithm of this expression for k = m − 1, we get: log(m) (tow(m, m)) ⩽ 1 + log m + log log m ⩽m

(because m ⩾ 4)

∗

Finally, since log (m) ⩽ m, we get for every integer m ⩾ 4: log∗ (tow(m, m)) ⩽ m + log∗ (log(m) (tow(m, m))) ⩽ m + log∗ (m) ⩽ 2m Now, let n ⩾ tow(4, 4), and let m := dlog∗ (n). Note that m ⩾ 4, so we have: log∗ (n) ⩽ log∗ (tow(m, m)) ⩽ 2m ⩽ 2dlog∗ (n) This finally proves that log∗ (n) = O(dlog∗ (n)).

◀

20

The local complexity of certifying parity

Proof of Theorem 14. Assume that o(log∗ n) different certificates are sufficient to certify an even number of vertices. For every integer m, let n := m + 2m − 1. The proof is the same as the proof of Theorem 11, but we just need to show that there exists an integer m such that m ⩾ f (2, c), where c is the number of different certificates (which is a function of n, so a function of m). By assumption, we have c = o(log∗ n). Since log∗ 2m = 1 + log∗ m, we have log∗ n = Θ(log∗ m). Thus, we also have c = o(log∗ m). By Lemma 15, we have c = o(dlog∗ m). By Theorem 13, we have f (2, c) ⩽ tow(2c, 2c). Let m be large enough, such that c ⩽ (dlog∗ m − 1)/2. Then, f (2, c) ⩽ tow(dlog∗ m − 1, dlog∗ m − 1) < m. The rest of the proof is identical as the proof of Theorem 11. ◀ ▶ Remark 16. The lower bound of Theorem 14 still holds in the following classes of graphs: (i) bipartite graphs; (ii) chordal graphs. Indeed, (i) follows from the fact that graphs Gm and G′m involved in the proof of Theorem 11 are bipartite. To prove (ii), we just need to change a bit the definition of Gm in the proof of Theorem 11, by adding all the edges between vertices of X. With this modification, the graph Gm becomes a split graph (that is, a graph whose vertices can be partitioned into a clique and an independent set) which is in particular chordal (that is, without any induced cycle of length at least 4). The proof still works identically, using the fact that gluing two chordal graphs by identifying one vertex in each gives another chordal graph.

AI Disclosure: We used an LLM to suggest alternative formulations in the introduction. The authors verified the correctness and originality of all content including references.

N. Bousquet, L. Feuilloley, J. Valenzuela, S. Zeitoun

References 1

2

3

4

5

6

7

8 9

10

11 12 13

14

15 16

Dan Alden Baterisna and Yi-Jun Chang. Optimal local certification on graphs of bounded pathwidth. In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC 2025, pages 99–109. ACM, 2025. doi:10.1145/3732772.3733503. Lélia Blin, Fedor V. Fomin, Pierre Fraigniaud, Sylvain Gay, Petr A. Golovach, Pedro Montealegre, Ivan Rapaport, and Ioan Todinca. What can be computed locally revisited: First-order logic on sparse graphs in distributed computing. In Proceedings of the 58th Annual ACM Symposium on Theory of Computing, STOC 2026, page To appear, 2026. Nicolas Bousquet, Linda Cook, Laurent Feuilloley, Théo Pierron, and Sébastien Zeitoun. Local certification of forbidden subgraphs. CoRR, abs/2402.12148, 2024. URL: https: //doi.org/10.48550/arXiv.2402.12148, doi:10.48550/ARXIV.2402.12148. Nicolas Bousquet, Laurent Feuilloley, and Sébastien Zeitoun. Complexity landscape for local certification. In 39th International Symposium on Distributed Computing, DISC 2025, LIPIcs, pages 18:1–18:21, 2025. URL: https://doi.org/10.4230/LIPIcs.DISC.2025.18, doi:10.4230/LIPICS.DISC.2025.18. 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, 2025. URL: https://doi.org/10.1137/24m1650041, doi:10.1137/24M1650041. Jé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, 2026. URL: https://doi.org/10.48550/arXiv.2602.12894, doi:10.48550/ARXIV.2602.12894. Linda Cook, Eun Jung Kim, and Tomás Masarík. A tight meta-theorem for LOCAL certification of MSO2 properties within bounded treewidth graphs. In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC 2025, pages 110–120. ACM, 2025. doi: 10.1145/3732772.3733562. Laurent Feuilloley. Introduction to local certification. Discret. Math. Theor. Comput. Sci., 23(3), 2021. URL: https://doi.org/10.46298/dmtcs.6280, doi:10.46298/DMTCS.6280. 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, 2022. doi:10.1145/3519270.3538416. Laurent Feuilloley, Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, Éric Rémila, and Ioan Todinca. Compact distributed certification of planar graphs. Algorithmica, 83(7):2215–2244, 2021. URL: https://doi.org/10.1007/s00453-021-00823-w, doi:10. 1007/S00453-021-00823-W. Laurent Feuilloley, Josef Erik Sedlácek, and Martin Slávik. Proving there is a leader without naming it. In SIROCCO ’26, page To Appear, 2026. arxiv: 2511.15491. Arnold Filtser and Orr Fischer. Near-resolution of the tradeoff conjecture in distributed proof labeling schemes. In PODC ’26, page To Appear, 2026. arxiv: 2605.19078. Pierre Fraigniaud, Frédéric Mazoit, Pedro Montealegre, Ivan Rapaport, and Ioan Todinca. Distributed certification for classes of dense graphs. In 37th International Symposium on Distributed Computing, DISC 2023, LIPIcs, pages 20:1–20:17. Schloss Dagstuhl - LeibnizZentrum für Informatik, 2023. URL: https://doi.org/10.4230/LIPIcs.DISC.2023.20, doi: 10.4230/LIPICS.DISC.2023.20. Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, and Ioan Todinca. A meta-theorem for distributed certification. Algorithmica, 86(2):585–612, 2024. URL: https://doi.org/10. 1007/s00453-023-01185-1, doi:10.1007/S00453-023-01185-1. 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. Ronald L Graham, Bruce L Rothschild, and Joel H Spencer. Ramsey theory. John Wiley & Sons, 1991.

21

22

The local complexity of certifying parity

17

18

19 20

Robert Hickingbotham. Odd colourings, conflict-free colourings and strong colouring numbers. Australas. J Comb., 87:160–164, 2023. URL: http://ajc.maths.uq.edu.au/pdf/87/ajc_v87_ p160.pdf. 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, doi:10.1007/ S00446-010-0095-3. Moni Naor and Larry J. Stockmeyer. What can be computed locally? SIAM J. Comput., 24(6):1259–1277, 1995. doi:10.1137/S0097539793254571. Yudi Setyawan. Combinatorial Number Theory: Results of Hilbert, Schur, Folkman, and Hindman. Simon Fraser University, 1998.