betaFeedback

WorksComputer Science

Tight Bounds for Anonymous Parity Certification

Abstract

Local certification is the task of verifying graph properties using certificates assigned to vertices and checked using only local information. A central question is which properties admit constant-size certificates, independently of network size. A fundamental test case is the parity of the network order. Bousquet, Feuilloley, Valenzuela, and Zeitoun (DISC 2026) showed that the complexity of certifying even order depends dramatically on the verification model. On arbitrary graphs, three bits per vertex suffice with unique identifiers and verification radius two. In the anonymous radius-one model, they established an Ω(log⁡log⁡∗n)Ω(\log\log^* n) lower bound and an O(log⁡n)O(\log n) upper bound. They also showed that constant-size certificates suffice in this model on bounded-expansion classes. In this paper, we settle the complexity of anonymous parity certification on general graphs and further investigate the role of graph sparsity. Our main contributions are: * We close the gap left by Bousquet et al., proving that the local complexity of certifying even order in the anonymous radius-one model is Θ(log⁡log⁡n)Θ(\log\log n) bits. * We show that on graphs of degeneracy at most dd, parity can be certified with O(log⁡d)O(\log d) bits, while Ω(log⁡log⁡d)Ω(\log\log d) bits are necessary. In particular, every class of bounded degeneracy admits constant-size certificates, strictly generalizing the result for bounded-expansion classes. * We show that constant-size certification cannot be guaranteed on nowhere-dense classes, a broader notion of sparsity that includes bounded expansion. We construct a fixed, subgraph-closed nowhere-dense class on which parity certification requires Θ(log⁡log⁡n)Θ(\log\log n) bits. Together, our results provide a more complete picture of anonymous parity certification on sparse graph classes, showing that its complexity depends on the particular structural notion of sparsity.

Introduction

Local certification is a distributed mechanism for verifying graph properties. An all-powerful prover assigns a certificate to every vertex, and each vertex decides whether to accept by inspecting its local neighborhood and the certificates it contains. A scheme is correct if every graph satisfying the property has an assignment accepted everywhere, whereas on a graph violating it, every assignment is rejected by at least one vertex. The central resource is the maximum number of certificate bits per vertex; see [8, 12, 14, 18] for background. Recent research has increasingly focused on the constant-size regime: which properties can be certified with O(1)O(1) bits per vertex, independently of the size of the network? Such properties are sometimes regarded as “local” from the certification perspective, even when their definitions are global [1].

One of the most basic questions in this direction is whether the number of vertices is even. Let EVEN denote this property. Parity is inherently global: changing the number of vertices by one changes the answer, potentially far away from any given vertex. Yet it can be remarkably easy to certify. On cycles, even order is equivalent to bipartiteness and can be certified with one bit per vertex. On trees, constant-size certificates also suffice, by aggregating subtree sizes modulo two. The challenge is to understand whether such small local proofs are possible on arbitrary graphs.

This question was recently investigated by Bousquet, Feuilloley, Valenzuela, and Zeitoun [2] (DISC 2026), who uncovered a striking dependence on the verification model and the underlying graph class. On general graphs, they showed that three bits suffice when vertices have unique identifiers and the verification radius is two. At the other extreme, they studied the anonymous radius-one model, which corresponds to the MULTISET model of local verification. In this model, a vertex sees only its own certificate and the multiset of its neighbors’ certificates, including multiplicities, but has no identifiers, port numbers, or knowledge of the graph order. They proved an Ω(log⁡log⁡∗n)\Omega(\log\log^* n) lower bound, against an O(log⁡n)O(\log n) upper bound. They also established that, on every graph class of bounded expansion, constant-size certificates suffice even in this restricted anonymous model. Bounded expansion is a robust notion of structural sparsity that includes, for example, bounded-degree and planar graphs.

Two natural questions remained. First, the gap between Ω(log⁡log⁡∗n)\Omega(\log\log^* n) and O(log⁡n)O(\log n) left the actual complexity of anonymous parity certification on general graphs essentially undetermined. Second, the bounded-expansion result raised a structural question: how far can constant-size parity certification be extended beyond bounded expansion, and which weaker notions of sparsity, if any, still guarantee it? These are the questions we address here.

Our results

Our first contribution settles the open problem of [2] for anonymous networks with verification radius one. We establish matching upper and lower bounds on the size of the certificates.

Theorem 1. There is an anonymous radius-one certification scheme for EVEN using O(log⁡log⁡n)O(\log\log n) bits per vertex.

Our scheme shows that the order of the network need not be encoded explicitly to certify its parity, even in the anonymous radius-one model. The natural question is whether the doubly logarithmic dependence can be reduced further. We show that it cannot, already on connected bipartite graphs.

Theorem 2. For every sufficiently large even nn, there is a connected bipartite nn-vertex graph GnG_n such that every accepting assignment of every correct anonymous radius-one verifier for

EVEN has a certificate of length Ω(log⁡log⁡n)\Omega(\log\log n). This remains true when correctness is required only on bipartite inputs.

Together, Theorems 1 and 2 show that certifying EVEN on connected nn-vertex graphs has local complexity Θ(log⁡log⁡n)\Theta(\log\log n). Thus parity has genuinely intermediate complexity in this model: constant-size certificates do not suffice, but the Θ(log⁡n)\Theta(\log n) bits needed to explicitly represent the graph order are unnecessary. The lower bound holds even under a bipartite promise.

Our second contribution strengthens the positive result of [2] by replacing bounded expansion with bounded degeneracy. Recall that a graph is dd-degenerate if every nonempty subgraph has a vertex of degree at most dd. This condition allows vertices of arbitrarily large degree but restricts the density of every subgraph. Crucially, every bounded-expansion class has bounded degeneracy, whereas the converse is false: for example, the class of one-subdivisions of complete graphs is 2-degenerate but does not have bounded expansion.

Theorem 3. The verifier of Theorem 1 admits O(log⁡d)O(\log d)-bit certificates on every connected even-order dd-degenerate graph, for every integer d≥2d \ge2, and constant-size certificates when d=1d = 1. It remains sound on arbitrary connected graphs and is not supplied with dd.

In particular, every graph class of bounded degeneracy admits constant-size certificates, strengthening the bounded-expansion result of [2]. The dependence on dd, however, cannot be removed altogether. Our next result shows that the certificate size must grow with dd, even on bipartite graphs and even when the verifier is only required to work under the dd-degeneracy promise.

Theorem 4. For every sufficiently large integer dd, there is a connected bipartite graph of even order and degeneracy at most $d on which every accepting assignment of every anonymous radius-one certification scheme for EVEN contains a certificate of length Ω(log⁡log⁡d)\Omega(\log\log d). This holds even when correctness is required only on connected bipartite dd-degenerate graphs.

The two bounds leave a gap in the optimal dependence on the degeneracy parameter, between Ω(log⁡log⁡d)\Omega(\log\log d) and O(log⁡d)O(\log d).

Our third contribution shows that the bounded-expansion theorem cannot be extended to all nowhere-dense classes. A graph class is nowhere dense if, for every fixed radius rr, there is a clique that cannot occur as an rr-shallow minor of any graph in the class. This is a broad notion of sparsity: every bounded-expansion class is nowhere dense, but the converse does not hold, and nowhere-dense classes may have unbounded degeneracy.

Theorem 5. There exists a fixed, subgraph-closed nowhere-dense class of graphs on which certifying EVEN in the anonymous radius-one model has local complexity Θ(log⁡log⁡n)\Theta(\log\log n).

In fact, our construction gives a bipartite class whose girth grows with the graph order. A precise description of this class, together with a quantitative lower bound, is given in § 6. Thus, the full difficulty of the unrestricted anonymous model persists even on graphs with arbitrarily large girth.

Taken together, these results give a substantially sharper picture of parity certification on sparse graph classes. The constant-size result extends beyond bounded expansion to all classes of bounded degeneracy, but it fails already on a fixed nowhere-dense class. Hence the positive phenomenon discovered in [2] is not explained by sparsity in general: the particular structural restriction matters. What remains open is the exact quantitative cost of parity certification as a function of degeneracy.

Proof ideas and techniques

Sharing contributions without identifying parents. Earlier anonymous schemes organize contributions by choosing a parent for each vertex. A color identifies that parent only if no other neighbor has the same color [2]. Enforcing this uniqueness can require many colors, making the parent descriptions expensive.

Our approach allows a contribution to be shared among several neighbors. For example, two senders with the same two receivers can each send half a unit to each receiver. Each sender sends one unit in total, and each receiver receives one unit, even though neither sender distinguishes between the receivers. Fractions allow us to coordinate whole-number totals without making individual choices.

The verifier checks that the amount sent minus the amount received is an odd integer at every vertex. Every payment appears once as an outgoing amount and once as an incoming amount, so these differences sum to zero. Since an odd number of odd integers cannot sum to zero, acceptance implies that the graph has even order.

The main task is to arrange these payments using short descriptions. Our sharing lemma coordinates fractional payments so that receivers obtain integer totals, using colors and fractions that take O(log⁡log⁡n)O(\log\log n) bits to describe. The prover applies the lemma between successive distance layers, working toward a chosen root. At each step, a vertex chooses what to send according to the parity of what it has already received. On bounded-degeneracy graphs, the same construction uses constant-size descriptions.

Changing parity without changing local views. A lower bound construction must change the number of vertices; changing edges alone cannot change parity. It must also leave every vertex with a local view that the verifier accepts. The earlier construction [2] achieves this using all nonempty subsets of a point set, resulting in exponentially many vertices. We obtain a smaller construction using intervals in an ordered point set. Each interval is represented by a vertex adjacent to the points it contains.

The key is to find two collections of intervals that cover every point equally often, but whose numbers of intervals have different parities. If all their interval vertices carry the same certificate, we can copy one collection and delete the other. Every point loses and gains the same number of neighbors with that certificate. Retained interval vertices keep their views, and new copies imitate existing vertices. All checks still pass, although the graph order changes parity.

Intervals provide a simple way to find such collections. When traversing a closed loop of interval endpoints, rightward and leftward steps cover every point equally often. If the loop has odd length, the two groups of steps have different parities. Thus a sound verifier must prevent an odd cycle whose intervals all carry the same certificate. A classical coloring bound [16] then forces a logarithmic number of distinct certificates. Because the construction has only polynomially many vertices, describing that many certificates requires Ω(log⁡log⁡n)\Omega(\log\log n) bits.

Preserving large girth through vertex splitting. For the nowhere-dense lower bound, we need a parity-changing operation that preserves large girth. Suppose three vertices carry the same certificate and one has a neighbor-certificate profile equal to the sum of the other two profiles. We can split that vertex into two, distributing its neighbors so that each replacement imitates one of the other vertices. Every old neighbor still sees one vertex with the original certificate. The order increases by one, and splitting cannot create a shorter cycle.

To force such a triple, we return to intervals. Their color-count profiles satisfy an exact identity: the profile of a long interval is the sum of the profiles of its two pieces. For every coloring of the point set, a counting argument finds an ordered sequence whose interval profiles are all sufficiently likely under random subset sampling. Sampling supplies many representatives of each profile, allowing us to remove short cycles while keeping all these representatives available. Color each interval’s endpoint pair by its representative’s certificate. An elementary Ramsey bound gives a monochromatic triangle, and hence the three equally certified profiles needed for splitting.

Related work

Sublogarithmic certification. Bousquet, Feuilloley, and Zeitoun [1] identified a Θ(log⁡log⁡n)\Theta(\log\log n) regime for an arithmetic property of anonymous path lengths, defined using products of consecutive primes, and proved a gap between constant and logarithmic complexity on anonymous cycles. Our result brings the same intermediate scale to a simple counting predicate on unrestricted connected graphs. Since parity has constant-size certificates on paths and cycles, its difficulty here comes from the richer range of possible topologies. A related result of Feuilloley, Sedláček, and Slávik [11] gives O(log⁡log⁡n)O(\log\log n)-bit certificates for at most one selected vertex when the minimum degree is at least αlog⁡2n\alpha\log^2 n, for a sufficiently large constant α\alpha. Their scheme uses identifiers and radius two, highlighting the different assumptions under which sublogarithmic certification becomes possible.

Structure and certificate size. Graph structure is a recurring theme in local certification, from certifying planarity [9] to logical metatheorems on tree-like graph classes [5, 10, 13]. On bounded-treewidth classes, these metatheorems progressed from O(log⁡2n)O(\log^2 n)-bit certificates [13] to O(log⁡n)O(\log n)-bit certificates for MSO2\mathrm{MSO}_2 properties [5]. For parity in the anonymous radius-one model, Bousquet et al. [2] obtained constant-size certificates on bounded-expansion classes using Hickingbotham’s conflict-free neighborhood colorings [17]. We extend this constant-size guarantee from bounded expansion to bounded degeneracy. However, replacing bounded expansion with nowhere denseness does not preserve the guarantee: on a fixed subgraph-closed nowhere-dense class, parity certification still has the Θ(log⁡log⁡n)\Theta(\log\log n) complexity of general graphs.

Combinatorial tools. Our construction draws on the theory of conflict-free and odd colorings [4, 6, 7, 20]. Conflict-free colors single out a neighbor, whereas odd colors need only occur an odd number of times in a neighborhood. Rational sharing adds another possibility: contributions can be distributed among indistinguishable neighbors while preserving integral totals. Conservation checks already appear in flow certification [18, 21]; the challenge here is to describe the transfers with short anonymous vertex certificates. The lower-bound techniques also have a broader reach. Chang, Lee, and Tsai [3] adapted the earlier parity construction to anonymous 2-vertex-connectivity, showing how neighborhood identities that preserve accepted local views can obstruct certification beyond counting predicates.

Discussion and open problems

We have determined the local complexity of EVEN in the anonymous radius-one model: Θ(log⁡log⁡n)\Theta(\log\log n) bits are necessary and sufficient in the worst case. Parity thus gives an elementary global property whose optimal certificate size is unbounded but sublogarithmic. The two proofs explain this scale from complementary directions. Rational sharing coordinates parity contributions without selecting unique parents, while the interval construction quantifies how much ambiguity any sound verifier must eliminate. The same verifier admits constant-size certificates on every class of bounded degeneracy. These results settle the dependence on graph order and leave several questions about structure and the verification model.

The Θ(log⁡log⁡n)\Theta(\log\log n) bound also holds, with a smaller leading constant in the lower bound, on a fixed subgraph-closed nowhere-dense class. Thus nowhere denseness alone does not guarantee constant-size certificates, even though bounded degeneracy does.

The dependence on degeneracy. Our structural bounds lie between Ω(log⁡log⁡d)\Omega(\log\log d) and O(log⁡(d+1))O(\log(d+1)). They show that degeneracy alone controls certificate size, but do not determine the optimal dependence on this parameter.

Open problem 1. What is the optimal local complexity of certifying Even on connected dd-degenerate graphs, as a function of dd? In particular, do O(log⁡log⁡(d+2))O(\log\log(d+2))-bit certificates suffice, independently of the graph order?

Our lower-bound witnesses have order Θ(d2)\Theta(d^{2}), so the general upper bound already gives O(log⁡log⁡d)O(\log\log d)-bit certificates on them. Consequently, they cannot establish a larger asymptotic lower bound in terms of dd. An Ω(log⁡d)\Omega(\log d) lower bound would require witnesses whose order exceeds every fixed polynomial in dd. Within our approach, improving the upper bound would require a more compact description of the sharing rules.

Identifiers and verification radius. Bousquet et al. [2] gave three-bit certificates when identifiers and radius two are both available. Our tight bound establishes the cost of imposing anonymity and radius one together. The intermediate cases, already asked about in [2], remain unresolved.

Open problem 2. What is the local complexity of certifying Even on arbitrary connected graphs (i) with identifiers and verification radius one, and (ii) anonymously with verification radius two? Do constant-size certificates suffice in either model?

Both models inherit our O(log⁡log⁡n)O(\log\log n) upper bound. The lower-bound modification uses anonymity to copy certified vertices without introducing new identifiers into their local views, and radius one to hide changes in their neighbors’ other incident edges. Extending the obstruction to either intermediate model therefore requires an additional idea. Resolving these cases would separate the roles of identifiers and observation radius in the cost of certifying parity.

Counting modulo other integers. Divisibility by a fixed integer, studied in [2], is a natural next setting in which to test the scope of our techniques.

Open problem 3. For a fixed integer k≥3k \ge3, what is the optimal certificate size for verifying that the order of a connected graph is divisible by kk in the anonymous radius-one model? Does the Θ(log⁡log⁡n)\Theta(\log\log n) bound hold for every such kk?

The conservation principle extends directly: if every vertex has integer net outflow congruent to one modulo kk, then summing the balances forces k∣nk \mid n. Constructing these balances with short anonymous labels, however, requires control of the residues modulo kk, beyond the odd–even distinction used here. For the lower bound, the profile-splitting construction also gives an Ω(log⁡log⁡n)\Omega(\log\log n) lower bound for divisibility by every fixed integer k≥2k \ge2, since it changes the order by exactly one. The remaining question is whether an O(log⁡log⁡n)O(\log\log n) upper bound holds for these moduli.

Model and definitions

Graphs and certification model

All graphs are finite, simple, and undirected; input graphs are connected. For G=(V,E)G=(V,E), write n=∣V∣n=|V|, NG(v)N_G(v) for the neighborhood of vv, deg⁡G(v)=∣NG(v)∣\deg_G(v)=|N_G(v)|, Δ(G)\Delta(G) for the maximum degree, and G[X]G[X] for the subgraph induced by X⊆VX \subseteq V. We omit the subscript GG when clear. All logarithms are base two. Write Z\mathbb{Z} and Q\mathbb{Q} for the integers and rationals, and 1A1_A for the indicator of a condition or the characteristic vector of a set.

A graph is kk-degenerate, for an integer k≥0k \ge0, if every nonempty subgraph has a vertex of degree at most kk. Equivalently, there is an ordering in which each vertex has at most kk later neighbors; the least such kk is its degeneracy. Orienting edges from earlier to later in this ordering gives an acyclic orientation of maximum outdegree at most kk.

The girth of a graph is the length of its shortest cycle, with girth infinity for forests. For an integer ρ≥0\rho\ge0, a depth-ρ\rho minor of GG is obtained from a subgraph of GG by contracting pairwise disjoint connected subgraphs of radius at most ρ\rho, measured within each contracted subgraph. A graph class C\mathcal{C} is nowhere dense if, for every integer ρ≥0\rho\ge0, there is an integer tt such that no graph in C\mathcal{C} contains KtK_t as a depth-ρ\rho minor [19].

Certificates and local verification. We use the anonymous model with verification radius one of [2]. A certificate assignment on GG is a map c:V→{0,1}∗c : V \to\{0,1\}^{*}, chosen by an external prover. The local view at a vertex vv is

view⁡G,c(v)=(c(v),{ ⁣{c(u):u∈N(v)} ⁣}).\operatorname{view}_{G,c}(v) = \left(c(v), \{\!\{c(u) : u \in N(v)\}\!\}\right).

where double braces denote a multiset. A verification algorithm is a deterministic function that takes this view and outputs accept or reject. The same function is used at every vertex and on every input graph. A graph is globally accepted if all its vertices accept. Vertices have no identifiers, ports, graph order, neighbor degrees, or information about edges between neighbors or their other incident edges. There are no computational restrictions on the prover or the verification function. In particular, the prover may assign different certificates to structurally indistinguishable vertices.

Certification schemes and local complexity. Let C\mathcal{C} be a graph class, let PP be a graph property on C\mathcal{C}, and let s:N→Ns : \mathbb{N} \to\mathbb{N}. A certification scheme for PP on C\mathcal{C} with local complexity ss consists of a verification algorithm satisfying the following two conditions:

  • Completeness. Every connected nn-vertex graph G∈CG \in\mathcal{C} satisfying PP admits a certificate assignment cc with ∣c(v)∣≤s(n)|c(v)| \le s(n) for every vertex vv, under which GG is globally accepted.

  • Soundness. For every connected graph G∈CG \in\mathcal{C} not satisfying PP, and every certificate assignment cc, at least one vertex rejects.

The class C\mathcal{C} is a promise: the verification algorithm may depend on C\mathcal{C} and PP, and no correctness requirement is imposed outside C\mathcal{C}. Unless a class is specified, C\mathcal{C} consists of all graphs. In this paper, P=EvenP = \mathrm{Even}: completeness concerns even-order graphs and soundness concerns odd-order graphs.

Rational transfers, encodings, and standard combinatorial facts

A transfer on an ordered edge (v,u)(v,u) contributes to the outgoing total at vv and the incoming total at uu. The net outflow Δ(v)\Delta(v) is outgoing minus incoming; an odd net outflow means Δ(v)∈2Z+1\Delta(v) \in2\mathbb{Z} + 1. All transfers used in the upper bounds are nonnegative rationals.

We fix a self-delimiting encoding of nonnegative integers. For t≥0t \ge0, let ℓ\ell be the binary length of t+1t+1 and encode tt as 1ℓ0bin⁡(t+1)1^{\ell}0\operatorname{bin}(t+1), using 2ℓ+1=O(log⁡(t+2))2\ell+1 = O(\log(t+2)) bits. Encode a nonnegative rational by its numerator and positive denominator in lowest terms, with zero represented by 0/10/1. If q∈[0,2)q \in[0,2) has reduced denominator at most kk, its numerator is less than 2k2k, so its encoding takes O(log⁡(k+1))O(\log(k+1)) bits.

We use the following standard facts.

Lemma 6 (Hall [15]). Let B=(S∪R,EB)B = (S \cup R, E_B) be a finite bipartite graph, and write NB(T)=⋃s∈TNB(s)N_B(T) = \bigcup_{s \in T} N_B(s) for T⊆ST \subseteq S. If ∣NB(T)∣≥∣T∣|N_B(T)| \ge|T| for every T⊆ST \subseteq S, then BB has a matching covering SS.

Lemma 7 (Degeneracy bound, Szekeres and Wilf [22]). Every finite dd-degenerate graph has a proper coloring with at most d+1d+1 colors.

Lemma 8 (Bipartite covers, Harary, Hsu, and Miller [16]). If rr bipartite subgraphs cover all edges of KtK_t, then r≥⌈log⁡t⌉r \ge\lceil\log t \rceil.

For a hypergraph H\mathcal{H}, write Δ(H)\Delta(\mathcal{H}) for the maximum number of hyperedges containing a vertex, and ε(H)\varepsilon(\mathcal{H}) for the minimum hyperedge size. A graph–hypergraph pair (F,H)(F,\mathcal{H}) has a common vertex set.

Lemma 9 (Dai, Ouyang, and Pirot [6 Theorem 5]). There is a universal constant C≥1C \ge1 such that the following holds. Let (F,H)(F,\mathcal{H}) be a finite graph–hypergraph pair, with D=Δ(H)≥2D = \Delta(\mathcal{H}) \ge2. If ε(H)>Clog⁡D\varepsilon(\mathcal{H}) > C \log D, then its vertex set admits a coloring that is proper on FF and has some color occurring an odd number of times in each hyperedge of H\mathcal{H}, using at most Δ(F)+Clog⁡D\Delta(F) + C \log D colors.

Upper bound in general graphs

Earlier anonymous schemes encode parents through conflict-free colors: a vertex selects a color unique among its predecessors [2]. This can be expensive even on sparse graphs. If there are mm receivers and one sender for every pair, all receivers need different colors. The resulting one-subdivision of KmK_m has Θ(m2)\Theta(m^2) vertices, so color names take Θ(log⁡n)\Theta(\log n) bits. Rational sharing avoids selecting a unique parent by allowing equal transfers to neighbors with the same color. We first construct transfers on a bipartite graph of senders and receivers, then apply this construction between consecutive BFS layers.

The sharing lemma

In a bipartite graph B=(S∪R,EB)B = (S \cup R, E_B), vertices of SS are senders and vertices of RR are receivers. A receiver coloring is odd at a sender if some color occurs an odd number of times among its neighbors. Each sender stores a base amount and a selected color; each receiver stores its own color. These labels determine the edge transfers, including when senders have identical neighborhoods.

Lemma 10 (Sharing lemma). Let B=(S∪R,EB)B = (S \cup R, E_B) be a finite bipartite graph on n≥2n \ge2 vertices, with senders SS and receivers RR. Assume every sender has a neighbor. There are receiver colors γr∈Z>02\gamma_r \in\mathbb{Z}_{>0}^2, rational base amounts qs∈[0,2)q_s \in[0,2), and selected colors as∈{0}∪Z>02a_s \in\{0\} \cup\mathbb{Z}_{>0}^2 such that the transfers

f(s,r)=qs+1γr=as(sr∈EB)f(s,r) = q_s + 1_{\gamma_r=a_s} \qquad(sr \in E_B)

satisfy

∑r∈NB(s)f(s,r)∈2Z+1(s∈S),∑s∈NB(r)f(s,r)∈Z(r∈R).(1)\begin{aligned} \sum_{r \in N_B(s)} f(s,r) &\in2\mathbb{Z}+1 &&(s \in S),\\ \sum_{s \in N_B(r)} f(s,r) &\in\mathbb{Z} &&(r \in R). \tag*{(1)} \end{aligned}

There are O(log⁡2(n+2))O(\log^2(n+2)) colors, each coordinate of a color is O(log⁡(n+2))O(\log(n+2)), and every base amount has reduced denominator O(log⁡(n+2))O(\log(n+2)). Each label γr\gamma_r, qsq_s, or asa_s therefore has an O(log⁡log⁡(n+2))O(\log\log(n+2))-bit encoding, with color coordinates encoded separately. The value as=0a_s=0 selects no color; equality of colors means equality in both coordinates, and no receiver color equals 00.

Proof. Let CC be the constant in Lemma 9. Take the least positive even integer b>Clog⁡(n+2)b > C\log(n+2), and put k=2b−1k = 2b - 1. Partition the senders into

Ssmall={s∈S:deg⁡B(s)≤k},Slarge={s∈S:deg⁡B(s)≥k+1}.(2)S_{\mathrm{small}} = \{s \in S : \deg_B(s) \le k\}, \qquad S_{\mathrm{large}} = \{s \in S : \deg_B(s) \ge k+1\}. \tag*{(2)}

We construct transfer rules for these two groups and then combine their receiver colorings.

Case 1: senders with at most kk neighbors. For each s∈Ssmalls \in S_{\mathrm{small}}, write ds=deg⁡B(s)d_s=\deg_B(s). Choose rational base amounts qsq_s such that

dsqs∈Z(s∈Ssmall),∑s∈NB(r)∩Ssmallqs∈Z(r∈R).d_s q_s \in\mathbb{Z}\quad(s \in S_{\mathrm{small}}), \qquad\sum_{s\in N_B(r)\cap S_{\mathrm{small}}} q_s \in\mathbb{Z}\quad(r \in R).

Thus both outgoing and incoming base totals are integral. The zero assignment is feasible. Among feasible assignments, maximize the number of senders with odd outgoing base total. Call these senders satisfied, and the others unsatisfied. A maximum exists because this number is an integer between zero and ∣Ssmall∣|S_{\mathrm{small}}|.

We claim that the unsatisfied senders can be matched to distinct receivers. Otherwise Hall’s theorem gives a set TT of unsatisfied senders with ∣NB(T)∣<∣T∣|N_B(T)|<|T|. Their neighborhood vectors are supported on fewer coordinates than there are vectors, so they are linearly dependent over Q\mathbb{Q}. Clearing denominators gives integers tst_s, not all zero, such that

∑s∈Tts1NB(s)=0.\sum_{s\in T} t_s \mathbf{1}_{N_B(s)}=0.

Let gg be the positive greatest common divisor of the nonzero integers dstsd_s t_s. Replace qsq_s by qs+ts/gq_s+t_s/g for s∈Ts\in T. At a receiver rr, the incoming total changes by 1g∑s∈T∩NB(r)ts=0\frac{1}{g}\sum_{s\in T\cap N_B(r)}t_s=0. At sender s∈Ts\in T, the outgoing total changes by the integer dsts/gd_s t_s/g. These integers have greatest common divisor one, so at least one is odd. At least one previously even total becomes odd, and all previously satisfied senders are unchanged. This contradicts maximality. Hence there is a matching covering the unsatisfied senders; let ρ(s)∈NB(s)\rho(s)\in N_B(s) be the receiver matched to ss. Figure 1 illustrates how a dependence preserves receiver totals while improving sender parities.

A rational perturbation in the maximality argument

Figure 1. A rational perturbation in the maximality argument. All three senders a,b,ca,b,c have neighborhood {u,v}\{u,v\}, so the unsatisfied set in (a) violates Hall’s condition. Its neighborhood vectors admit the dependence t=(−1,1,0)t=(-1,1,0); since every sender has degree two, g=2g=2. Adding t/gt/g to the base amounts gives (b): each receiver’s incoming total is unchanged, but two senders become satisfied as their outgoing totals change from even to odd. Thus (a) cannot maximize the number of satisfied senders.

Subtract an even integer from each qsq_s to put it in [0,2)[0,2). All incoming and outgoing totals change by even integers, preserving integrality and parity. Since dsqsd_s q_s is integral, the reduced denominator of qsq_s divides ds≤kd_s\leq k, and its numerator is less than 2ds2d_s. Thus the base amount takes O(log⁡(k+1))O(\log(k+1)) bits.

To make a unit correction at each unsatisfied sender, form an auxiliary graph KsmallK_{\mathrm{small}} on the receivers. For every such sender ss, join ρ(s)\rho(s) to all other vertices of NB(s)N_B(s). For X⊆RX\subseteq R, every edge of Ksmall[X]K_{\mathrm{small}}[X] is contributed by a matched receiver in XX. These receivers are distinct and each contributes at most k−1k-1 edges, so

∣E(Ksmall[X])∣≤(k−1)∣X∣.|E(K_{\mathrm{small}}[X])|\leq(k-1)|X|.

The graph KsmallK_{\mathrm{small}} is therefore (2k−2)(2k - 2)-degenerate. Lemma 7 gives a proper coloring χ\chi with 2k−12k - 1 colors. Each matched receiver has a color unique among its sender’s neighbors. Select this color at an unsatisfied sender, adding exactly one to its outgoing total. Select no color at a satisfied sender. Every sender in this case now sends an odd integer total, and receiver totals remain integral.

Case 2: senders with at least 2b2b neighbors. Let H\mathcal{H} be the hypergraph on RR whose hyperedges are the distinct neighborhoods NB(s)N_B(s), for s∈Slarges \in S_{\mathrm{large}}. Set D=Δ(H)D = \Delta(\mathcal{H}), taking D=0D = 0 if there are no hyperedges. A receiver belongs to at most one hyperedge per large sender, so D≤∣Slarge∣≤nD \leq|S_{\mathrm{large}}| \leq n.

If D≤1D \leq1, the distinct neighborhoods are pairwise disjoint. Give one receiver in each such neighborhood color one and all remaining receivers color two. This is odd at every large sender; if there are no large senders, any coloring suffices.

If D≥2D \geq2, apply Lemma 9 to the pair (F,H)(F, \mathcal{H}), where F=(R,∅)F = (R, \varnothing) is the edgeless graph on the receivers. The parameters in the lemma satisfy

Δ(F)=0,\Delta(F) = 0,
ε(H)=min⁡s∈Slargedeg⁡B(s)≥2b>Clog⁡(n+2)>Clog⁡D,\varepsilon(\mathcal{H}) = \min_{s \in S_{\mathrm{large}}} \deg_B(s) \geq2b > C \log(n + 2) > C \log D,

and the lemma supplies an odd coloring of H\mathcal{H} with at most Clog⁡D<bC \log D < b colors. Allowing unused colors, both cases therefore give a coloring h:R→{1,…,2b}h : R \to\{1, \ldots, 2b\} that is odd at every sender in SlargeS_{\mathrm{large}}: each sender’s neighborhood is a hyperedge, including when several senders have the same neighbors.

Combining the receiver colorings. Give each receiver r∈Rr \in R the ordered-pair color γr=(h(r),χ(r))\gamma_r = (h(r), \chi(r)). This is a common refinement of the two colorings: two receivers have the same color precisely when they agree in both coordinates. There are at most 2b(2k−1)=O(log⁡2(n+2))2b(2k - 1) = O(\log^2(n + 2)) color pairs. For a satisfied sender in SsmallS_{\mathrm{small}}, retain qsq_s and set as=0a_s = 0. For an unsatisfied sender, retain qsq_s and select the refined color of ρ(s)\rho(s). This receiver still has a color unique in NB(s)N_B(s), so all transfers from low-degree senders are unchanged.

For a sender in SlargeS_{\mathrm{large}}, an odd hh-color class in its neighborhood splits into refined color classes. At least one remains odd. Set qs=0q_s = 0 and select that refined color as asa_s. This sends an odd integer total and contributes only integers at receivers. The low-degree senders already gave integral receiver totals, proving (1).

Every reduced denominator is at most k=O(log⁡(n+2))k = O(\log(n + 2)); its numerator is less than 2k2k because 0≤qs<20 \leq q_s < 2. The two color coordinates are at most 2b2b and 2k−12k - 1, respectively, both O(log⁡(n+2))O(\log(n + 2)). Encoding the coordinates separately, and using a constant-size tag to distinguish a selected pair from 00, gives O(log⁡log⁡(n+2))O(\log\log(n + 2)) bits for each color label. The rational bounds give the same bound for each base amount.

The certification scheme

Theorem 1. There is an anonymous radius-one certification scheme for EVEN using O(log⁡log⁡n)O(\log\log n) bits per vertex.

Proof. Certificate and verifier. A certificate is a four-tuple (λ,γ,q,a)(\lambda, \gamma, q, a), where λ∈{0,1,2}\lambda\in\{0,1,2\} is a layer label, γ∈Z>02\gamma\in\mathbb{Z}_{>0}^{2} is a color, q∈Q∩[0,2)q \in\mathbb{Q} \cap[0,2) is a base amount, and a∈{0}∪Z>02a \in\{0\} \cup\mathbb{Z}_{>0}^{2} is a selected color. Encode λ\lambda in two bits. Encode γ\gamma by concatenating the self-delimiting encodings of its two positive coordinates, using the integer encoding from the preliminaries. Record qq by its numerator and positive denominator in lowest terms, using the same integer encoding. Encode aa with a tag bit: 0 represents no selected color, and 1 is followed by the two encoded coordinates of the selected color. A certificate is malformed if its fields cannot be decoded, violate the stated ranges, record a fraction that is not in lowest terms, or leave unused trailing bits. Color equality is coordinatewise. Since no receiver color is 0, the selected color a=0a=0 always means that no extra unit is sent.

For an arbitrary certificate assignment, call a neighbor uu of vv a predecessor when λu≡λv−1(mod3)\lambda_u \equiv\lambda_v-1 \pmod{3}, and a successor when λu≡λv+1(mod3)\lambda_u \equiv\lambda_v+1 \pmod{3}. Use subscripts to indicate the vertex supplying a field and write pv(u)=qv+1γu=avp_v(u)=q_v+1_{\gamma_u=a_v}. A vertex rejects if any certificate in its local view is malformed. Otherwise it checks

Δ(v):=∑u∈N(v)λu≡λv−1(mod3)pv(u)⏟sent to predecessors−∑u∈N(v)λu≡λv+1(mod3)pu(v)⏟received from successors∈2Z+1.(3)\Delta(v):= \underbrace{\sum_{\substack{u\in N(v)\\ \lambda_u\equiv\lambda_v-1\pmod{3}}}p_v(u)}_{\text{sent to predecessors}} - \underbrace{\sum_{\substack{u\in N(v)\\ \lambda_u\equiv\lambda_v+1\pmod{3}}}p_u(v)}_{\text{received from successors}} \in2\mathbb{Z}+1. \tag*{(3)}

The transfers are nonnegative rationals. The vertex computes its net outflow exactly and checks that it is an odd integer; a noninteger difference causes rejection. Both sums are computable from the local view: a neighbor’s fields determine its term, and repeated certificates contribute with their multiplicity. Three residues distinguish the two directions along consecutive layers; only these constant-size residues are stored, rather than full distances.

Soundness. Each transfer is counted once positively at its sender and once negatively at its receiver; edges between equal residues are ignored. This holds for arbitrary certificate assignments, regardless of whether the residues describe actual layers. If every vertex accepts, conservation gives

0=∑v∈VΔ(v)≡n(mod2),0=\sum_{v\in V}\Delta(v)\equiv n\pmod{2},

because each summand is an odd integer. Thus nn is even.

Completeness. Choose a root rr in an even-order graph and let

Li={v:dist⁡(r,v)=i}(i≥0),L−1=∅,L_i=\{v:\operatorname{dist}(r,v)=i\}\quad(i\geq0),\qquad L_{-1}=\varnothing,

be its BFS layers. Give each vertex its layer number modulo three. Every edge joins equal or consecutive layers, and every nonroot vertex has a neighbor in the preceding layer.

Process Lh,Lh−1,…,L1L_h,L_{h-1},\ldots,L_1, where hh is the maximum distance from the root; the root will be handled last. Once a vertex v∈Liv\in L_i has received an integer amount S(v)=∑w∈N(v)∩Li+1pw(v)S(v)=\sum_{w\in N(v)\cap L_{i+1}}p_w(v) from the next layer, its outgoing total must have parity opposite to S(v)S(v). If S(v)S(v) is odd, set qv=av=0q_v=a_v=0: the vertex sends zero, so its net outflow is odd. Call vertices with even S(v)S(v) active, and let SiS_i be the active vertices of LiL_i.

Form the bipartite graph BiB_i with parts SiS_i and Li−1L_{i-1}, containing all edges of GG between these parts. Its senders are the active vertices and its receivers are the vertices of the preceding layer. It has at most nn vertices, and every sender has a receiver neighbor. If Si≠∅S_i\ne\varnothing, apply Lemma 10 to BiB_i: store its receiver colors on Li−1L_{i-1} and its base amounts and selected colors on SiS_i. On an edge vuvu of BiB_i, its transfer f(v,u)f(v,u) is exactly the amount pv(u)p_v(u) computed by the verifier. Every active vertex sends an odd integer total, and every vertex of Li−1L_{i-1} receives an integer amount. This continues the induction, starting with zero incoming totals at the deepest layer. If Si=∅S_i=\varnothing, all transfers from that layer are zero and all vertices of the preceding layer may be given color (1,1)(1,1). Any color not assigned by this procedure may be set to (1,1)(1,1).

The color of a vertex is chosen when the next layer is processed; its base amount and selected color are chosen when its own layer is processed. Every nonroot vertex now has an odd integer net outflow: active vertices send an odd total after receiving an even total, and inactive vertices send zero after receiving an odd total. Give the root q=a=0q=a=0. All other checks already hold, so conservation forces its net outflow to be Δ(r)=−∑v≠rΔ(v)\Delta(r)=-\sum_{v\ne r}\Delta(v). This is an odd integer because n−1n-1 is odd. This gives an accepting assignment.

Certificate size. By the sharing lemma, each color, base amount, and selected color can be encoded in O(log⁡log⁡n)O(\log\log n) bits. The layer label takes a constant number of bits. A fixed self-delimiting encoding preserves this asymptotic bound. Thus an anonymous radius-one verifier uses O(log⁡log⁡n)O(\log\log n) certificate bits. Figure 2 illustrates the construction, including fractional transfers and a unit correction.

Rational sharing on a six-vertex graph

Figure 2. Rational sharing on a six-vertex graph. In the first sharing step, the top vertices are senders and uu, vv are receivers; each sender is adjacent to both receivers. The orange edge adds one unit to the selected color; dashed edges carry zero. The integer receipts determine which receivers become active senders to the preceding layer. Every net outflow is odd, and their sum is zero.

Lower bound

The earlier lower bound [2] uses all nonempty subsets of an mm-point set, giving exponentially many vertices, and a finite-unions argument. We use only intervals, giving quadratically many vertices. An odd cycle of interval endpoints yields a parity-changing modification that preserves local views, and a bipartite-cover count then gives the quantitative certificate bound.

The interval incidence construction

For m≥1m \ge1, take the ordered set of points P={1,…,m}P = \{1,\ldots,m\}. The graph HmH_m has a point vertex xtx_t for each t∈Pt \in P and an interval vertex yijy_{ij} for every $0 \le i < j \le m$, adjacent exactly to {xi+1,…,xj}\{x_{i+1},\ldots,x_j\}. The corresponding subset of PP is the discrete interval (i,j]={i+1,…,j}(i,j] = \{i+1,\ldots,j\}. The endpoint indices $0,\ldots,m$ specify the boundaries of these intervals; they do not add vertices to HmH_m. The graph HmH_m is the bipartite incidence graph of these intervals: the two parts consist of point vertices and interval vertices. This graph is connected and bipartite, with Nm=m+(m+12)=m(m+3)2N_m = m + \binom{m+1}{2} = \frac{m(m+3)}{2} vertices. When m≡1(mod4)m \equiv1 \pmod{4}, its order is even. Indeed, y0my_{0m} is adjacent to every point vertex, and every other interval vertex has a nonempty set of point neighbors, proving connectedness.

Fix a sufficiently large even nn. Choose the largest m≡1(mod4)m \equiv1 \pmod{4} with Nm≤nN_m \le n, and attach n−Nmn-N_m leaves to the point vertex x1x_1. Call the resulting graph GnG_n. It is connected and bipartite of order nn. Moreover Nm+4−Nm=4m+14N_{m+4}-N_m = 4m+14, so n=Nm+O(m)n = N_m + O(m) and m=Θ(n)m = \Theta(\sqrt{n}). These additional leaves give a graph for every sufficiently large even nn.

Consider any accepting certificate assignment on GnG_n. Introduce a separate complete graph Km+1K_{m+1} with vertex set {0,…,m}\{0,\ldots,m\}, and color its edge ijij by the certificate of yijy_{ij}. This auxiliary graph is not part of the input graph GnG_n. Its vertices are the interval endpoints, whereas the two parts of HmH_m represent points and intervals. The input graph GnG_n remains bipartite even when the auxiliary graph contains odd cycles.

A modification preserving local views

The following lemma is the key local-view argument. A cycle of endpoints gives two collections of intervals that cover each point equally often, allowing additions and deletions of interval vertices to cancel at every point vertex.

Lemma 11. For every certificate bb, the subgraph of the auxiliary graph formed by the edges of color bb is bipartite.

Proof. Suppose that it contains a simple odd cycle t0,t1,…,tℓ=t0t_0,t_1,\ldots,t_\ell=t_0. For its aath edge, let εa=1\varepsilon_a=1 if ta>ta−1t_a>t_{a-1} and εa=−1\varepsilon_a=-1 if ta<ta−1t_a<t_{a-1}, and write

Ia=(min⁡(ta−1,ta),max⁡(ta−1,ta)].I_a=\left(\min(t_{a-1},t_a),\max(t_{a-1},t_a)\right].

The interval vertices corresponding to these edges all have certificate bb. For 0≤t≤m0\le t\le m, let pt=1{1,…,t}∈Zmp_t=\mathbf{1}_{\{1,\ldots,t\}}\in\mathbb{Z}^m; in particular, p0=0p_0=0. These vectors record the points at most tt. By the definition of IaI_a and εa\varepsilon_a it holds that εa1Ia=pta−pta−1\varepsilon_a\mathbf{1}_{I_a}=p_{t_a}-p_{t_{a-1}}. Consequently

∑a=1ℓεa1Ia=0.(4)\sum_{a=1}^{\ell}\varepsilon_a\mathbf{1}_{I_a}=0. \tag*{(4)}

The differences sum to zero because each vector ptap_{t_a} appears once with each sign as we go around the cycle. Call an interval positive if εa=1\varepsilon_a=1 and negative if εa=−1\varepsilon_a=-1. Equation (3) says that each point is covered equally often by positive and negative intervals, even though their total number is odd. Figure 3 gives a five-cycle example.

Auxiliary cycle before and after a parity-changing modification

Figure 3. An odd cycle gives a parity-changing modification. All five interval vertices have certificate bb. The traversal 0,1,3,4,2,00,1,3,4,2,0 makes A,B,CA,B,C positive and D,ED,E negative. Delete D,ED,E and add the dashed copies A′,B′,C′A',B',C'. Each point vertex loses and gains one neighbor with certificate bb, while the order increases by one. Unshown vertices and edges are unchanged.

Modify the graph and its certificate assignment as follows. For every εa=−1\varepsilon_a=-1, delete the corresponding interval vertex. For every εa=1\varepsilon_a=1, add one new copy of that interval vertex, with certificate bb and the same point neighbors. Cycle edges are distinct, so the modifications are well defined. The resulting graph is still simple and bipartite: the copies are new vertices adjacent only to point vertices, even when their neighbor sets coincide with those of existing vertices.

At each point vertex, the change in the number of neighbors with certificate bb is zero by (3). All other neighbor-certificate multiplicities are unchanged. Its local view is therefore unchanged. Every retained interval vertex and every leaf added when constructing GnG_n keeps its original local view. Each copy has the same local view as the vertex it copies. All vertices therefore accept.

The order changes by ∑aεa\sum_a\varepsilon_a, which is odd because ℓ\ell is odd. The modified graph thus has odd order. Some connected component has odd order and all its vertices still accept: taking a component changes no local view, and the verifier is not given the graph order. This contradicts soundness. There is therefore no odd cycle in the subgraph of color bb, so it is bipartite. □\square

Counting certificates

Theorem 2. For every sufficiently large even nn, there is a connected bipartite nn-vertex graph GnG_n such that every accepting assignment of every correct anonymous radius-one verifier for EVEN has a certificate of length Ω(log⁡log⁡n)\Omega(\log\log n). This remains true when correctness is required only on bipartite inputs.

Proof. Let rr be the number of distinct certificates on interval vertices. By the preceding argument, their endpoint color classes are bipartite subgraphs whose edge sets partition Km+1K_{m+1}. Lemma 8 therefore gives r≥⌈log⁡(m+1)⌉r \ge\lceil\log(m+1) \rceil. This invokes the classical counting bound; the local-view modification above is what makes it applicable to certificates. If all certificates in the assignment have length at most ss, then r≤∑j=0s2j<2s+1r \le\sum_{j=0}^{s}2^j < 2^{s+1}. Since m=Θ(n)m=\Theta(\sqrt{n}), this yields

s≥log⁡log⁡(m+1)−1=Ω(log⁡log⁡n).s \ge\log\log(m+1)-1=\Omega(\log\log n).

Bounds parameterized by degeneracy

We now prove bounds for certifying EVEN on dd-degenerate graphs. In the general construction, the description of a transfer depends on the order of the bipartite graph used at each layer. We replace this dependence by degeneracy. The key is that every graph BiB_i between active vertices and their predecessors is a subgraph of the input graph. Its degeneracy is thus at most dd, even though a sender may have arbitrarily many receiver neighbors. The certificate format, BFS induction, and conservation check remain unchanged. For the lower bound, we check that the interval modification preserves the promised class.

Sharing on a dd-degenerate bipartite graph

The low-degree case of Lemma 10 already works with any prescribed degree bound. For senders of higher degree, degeneracy gives a receiver coloring with a unique color in each neighborhood, replacing the odd-coloring theorem used in the general proof.

Lemma 12. Let d≥1d\ge1 be an integer and let B=(S∪R,EB)B=(S\cup R,E_B) be a finite dd-degenerate bipartite graph, with senders SS and receivers RR. Assume every sender has a neighbor, and put Md=2d2+6d−1M_d=2d^2+6d-1. There are receiver colors γr∈{1,…,Md}×{1}\gamma_r\in\{1,\ldots,M_d\}\times\{1\}, base amounts qs∈Q∩[0,2)q_s\in\mathbb{Q}\cap[0,2) with reduced denominator at most 2d2d, and selected colors as∈{0}∪({1,…,Md}×{1})a_s\in\{0\}\cup(\{1,\ldots,M_d\}\times\{1\}) such that

f(s,r)=qs+1γr=as(sr∈EB)f(s,r)=q_s+\mathbf{1}_{\gamma_r=a_s}\qquad(sr\in E_B)

satisfies (1): every sender sends an odd integer total, and every receiver receives an integer total. Each label has an O(log⁡(d+1))O(\log(d+1))-bit encoding.

Proof. Partition the senders by degree:

Ssmall={s∈S:deg⁡B(s)≤2d},Slarge={s∈S:deg⁡B(s)≥2d+1}.S_{\mathrm{small}} = \{s \in S : \deg_B(s) \le2d\}, \qquad S_{\mathrm{large}} = \{s \in S : \deg_B(s) \ge2d + 1\}.

Low-degree senders: reuse the rational construction. Apply the maximality and matching argument from Case 1 in the proof of Lemma 10, with degree bound 2d2d, to B[Ssmall∪R]B[S_{\mathrm{small}} \cup R]. It gives rational base amounts qs∈[0,2)q_s \in[0,2) with integer outgoing totals deg⁡B(s)qs\deg_B(s)q_s and integer incoming totals at all receivers. The reduced denominator divides deg⁡B(s)\deg_B(s) and is therefore at most 2d2d. The unsatisfied senders, whose outgoing base totals are even, have a matching to distinct receivers ρ(s)∈NB(s)\rho(s) \in N_B(s).

Keep the auxiliary graph KsmallK_{\mathrm{small}} joining each matched receiver ρ(s)\rho(s) to the other neighbors of ss, and postpone its coloring. The same counting argument gives

∣E(Ksmall[X])∣≤(2d−1)∣X∣(X⊆R).(5)|E(K_{\mathrm{small}}[X])| \le(2d-1)|X| \qquad(X \subseteq R). \tag*{(5)}

This part of the proof changes only the degree threshold.

High-degree senders: use degeneracy. Orient the whole graph BB in a degeneracy ordering, so every vertex has outdegree at most dd. This is an auxiliary orientation for choosing the colors; transfers will still go from senders to receivers, regardless of these directions. For s∈Slarges \in S_{\mathrm{large}}, let Os={r∈NB(s):r→s}O_s = \{r \in N_B(s) : r \to s\}. Given BB is dd-degenerate, at most dd edges leave ss in the auxiliary orientation, so at most dd of its receivers are outside OsO_s. In particular, ∣NB(s)∖Os∣≤d|N_B(s) \setminus O_s| \le d and since deg⁡B(s)≥2d+1\deg_B(s) \ge2d+1, it follows that ∣Os∣≥d+1|O_s| \ge d+1. Each receiver belongs to at most dd of the neighborhoods OsO_s, since each membership uses an edge leaving that receiver. These are the two consequences of degeneracy used in the construction: few exceptions at a sender, and bounded participation at a receiver. Figure 4 illustrates how the first bound ensures that a candidate color does not recur outside OsO_s.

Ensuring a unique color when $d=2$

Figure 4. Ensuring a unique color when d=2d = 2. In (a), the orientation has at most two edges leaving ss; all other receivers lie in OsO_s. The three blue candidates form TsT_s. In (b), each candidate is adjacent in KlargeK_{\mathrm{large}} to every other receiver of OsO_s, so a proper coloring makes its color unique there. The two exceptional receivers can repeat at most two candidate colors; the double-circled candidate retains a color unique in the whole neighborhood. Arrows in (a) show only the auxiliary orientation, not the direction of transfers.

For each s∈Slarges \in S_{\mathrm{large}}, arbitrarily choose d+1d+1 candidate receivers Ts⊆OsT_s \subseteq O_s. Candidates may be shared by different senders. Form a graph KlargeK_{\mathrm{large}} on RR by joining each candidate in TsT_s to every other receiver in OsO_s, for every such ss. For X⊆RX \subseteq R,

∣E(Klarge[X])∣≤(d+1)∑s∈Slarge∣Os∩X∣≤d(d+1)∣X∣.(6)\begin{aligned} |E(K_{\mathrm{large}}[X])| &\le(d+1)\sum_{s \in S_{\mathrm{large}}}|O_s \cap X| \\ &\le d(d+1)|X|. \tag*{(6)} \end{aligned}

The first inequality bounds each sender’s contribution by d+1d+1 stars on Os∩XO_s \cap X; counting an edge repeatedly only increases the bound. The second uses the participation bound at receivers.

A common coloring and the transfers. Let K=Ksmall∪KlargeK = K_{\mathrm{small}} \cup K_{\mathrm{large}}. The two edge bounds give

∣E(K[X])∣≤(d2+3d−1)∣X∣(X⊆R).|E(K[X])| \le(d^2+3d-1)|X| \qquad(X \subseteq R).

Every nonempty induced subgraph has a vertex of degree at most 2d2+6d−22d^2+6d-2. Lemma 7 therefore gives a proper coloring c:R→{1,…,Md}c : R \to\{1,\ldots,M_d\}. Give each receiver the color γr=(c(r),1)\gamma_r = (c(r),1) to use the same ordered-pair format as in Lemma 10. This receiver coloring is proper on KK and uses at most MdM_d color pairs.

For each satisfied sender in SsmallS_{\mathrm{small}}, set as=0a_s = 0. For each unsatisfied one, select as=γρ(s)a_s = \gamma_{\rho(s)}. The matched receiver has a color unique in NB(s)N_B(s), so this adds exactly one to the even outgoing base total.

For a sender in SlargeS_{\mathrm{large}}, its d+1d+1 candidates have distinct colors, each occurring exactly once in OsO_s. The at most dd exceptional receivers in NB(s)∖OsN_B(s) \setminus O_s can repeat at most dd of those colors. Hence one candidate still has a color unique among all neighbors of ss (see Figure 4). Set qs=0q_s = 0 and select that color as asa_s. This sender sends exactly one unit.

All senders now have odd integer outgoing totals. Incoming totals remain integral because the low-degree base contributions were integral and all corrections are integers. There are O(d2)O(d^2) color pairs, whose first coordinates are at most MdM_d and whose second coordinates equal one. Each base amount has denominator at most 2d2d and numerator less than 4d4d. Encoding the color coordinates separately, with a tag for the selected color, gives O(log⁡(d+1))O(\log(d+1)) bits for each label.

The upper bound and certificate size

Theorem 3. The verifier of Theorem 1 admits O(log⁡d)O(\log d)-bit certificates on every connected even-order dd-degenerate graph, for every integer d≥2d \ge2, and constant-size certificates when d=1d = 1. It remains sound on arbitrary connected graphs and is not supplied with dd.

Proof. Use exactly the certificate (λ,γ,q,a)(\lambda,\gamma,q,a) and verifier of Theorem 1. In particular, dd is not an input or a certificate field, and the verifier does not check degeneracy.

For completeness, choose BFS layers in a connected even-order dd-degenerate graph. Repeat the same induction from the deepest layer toward the root. At step ii, form the bipartite graph BiB_i from the general construction: the active vertices of LiL_i send to their neighbors in Li−1L_{i-1}. Since BiB_i is a subgraph of the input graph, it is dd-degenerate.

Apply Lemma 12 to BiB_i in place of Lemma 10. Active vertices send odd integer totals; inactive vertices, having received odd integer totals, send zero. Each vertex of the preceding layer receives an integer total. The same induction gives odd integer net outflow at every nonroot vertex, and conservation gives an odd integer net outflow at the root because the graph has even order. As before, each vertex gets its receiver color when the next layer is processed, and its base amount and selected color when its own layer is processed.

The layer residue takes two bits. Each receiver color or selected color pair has first coordinate at most Md=O(d2)M_d = O(d^2) and second coordinate one; a selected color may also be 0. The rational numerator and denominator are O(d)O(d). The fixed encoding of the certificate therefore takes O(log⁡(d+1))O(\log(d+1)) bits in total, including the tag bit for the selected color. Soundness is unchanged: transfers cancel globally for arbitrary certificates, without any degeneracy assumption.

Both upper bounds use the same verifier and encoding. Consequently, on an nn-vertex even-order graph of degeneracy at most dd, this one verifier admits certificates of

O(min⁡{log⁡log⁡(n+2),log⁡(d+1)})O(\min\{\log\log(n+2),\log(d+1)\})

bits. No scheme-selection field is needed: the prover may use either completeness construction, and neither nn nor dd is trusted input.

A lower bound within the degeneracy promise

The interval construction already has the appropriate degeneracy when its number of points is proportional to dd. To obtain a lower bound under a class promise, we must also ensure that the modification used against soundness stays within that class.

Theorem 4. For every sufficiently large integer dd, there is a connected bipartite graph of even order and degeneracy at most dd on which every accepting assignment of every anonymous radius-one certification scheme for Even contains a certificate of length Ω(log⁡log⁡d)\Omega(\log\log d). This holds even when correctness is required only on connected bipartite dd-degenerate graphs.

Proof. For a sufficiently large integer dd, let m=max⁡{j≤d:j≡1(mod4)}m=\max\{j\le d:j\equiv1\pmod{4}\}. Use the interval incidence graph HmH_m from § 4; it is connected, bipartite and its order m(m+3)/2m(m+3)/2 is even. Every interval vertex has degree at most mm. Deleting all interval vertices first and then the independent point vertices gives an mm-degeneracy ordering, so HmH_m is dd-degenerate.

Fix a verifier correct on connected bipartite dd-degenerate graphs and any accepting assignment on HmH_m. As in the general lower bound, color edge ijij of the auxiliary Km+1K_{m+1} by the certificate of yijy_{ij}. Each certificate class must be bipartite. Indeed, the argument in Lemma 11 turns an odd cycle of one color into interval deletions and copies that preserve every local view and change the parity of the order. The modified graph still has the same mm point vertices, and every interval vertex still has degree at most mm. The same deletion ordering proves that it remains mm-degenerate. Every connected component is thus bipartite and dd-degenerate. An odd-order component accepted everywhere would contradict soundness even within the promised class.

If rr distinct certificates occur on interval vertices, Lemma 8 gives r≥⌈log⁡(m+1)⌉r\ge\lceil\log(m+1)\rceil. If all certificates have length at most ss, there are fewer than 2s+12^{s+1} possible strings. Hence

s≥log⁡log⁡(m+1)−1=Ω(log⁡log⁡(d+1)),s\ge\log\log(m+1)-1=\Omega(\log\log(d+1)),

where the asymptotic equality follows from d−4<m≤dd-4<m\le d. The argument applies to every accepting assignment and permits a different verifier for each fixed value of dd.

The witnesses have order Θ(d2)\Theta(d^2) and actual degeneracy Θ(d)\Theta(d). For t=(m+1)/2t=(m+1)/2, the first tt point vertices and the prefix interval vertices y0jy_{0j} with t≤j≤mt\le j\le m induce Kt,tK_{t,t}. Thus their degeneracy is at least tt and at most mm. The lower bound therefore concerns the structural parameter itself, rather than an unnecessarily large upper estimate for it.

A lower bound on a nowhere-dense class

The bounded-degeneracy upper bound shows that many sparse classes admit constant-size certificates. We now show that the general Θ(log⁡log⁡n)\Theta(\log\log n) bound remains tight on a fixed, subgraph-closed, bipartite nowhere-dense class.

Theorem 5. There exists a fixed, subgraph-closed nowhere-dense class of graphs on which certifying Even in the anonymous radius-one model has local complexity Θ(log⁡log⁡n)\Theta(\log\log n).

We now give a more explicit version of Theorem 5, identifying a concrete nowhere-dense class and providing a quantitative lower bound.

Lemma 13. Fix 0<α<10 < \alpha< 1, and let

Cα={G:G is bipartite and girth⁡(G)≥(log⁡(∣V(G)∣+2))α}.\mathcal{C}_{\alpha} = \{G : G\text{ is bipartite and }\operatorname{girth}(G) \geq(\log(|V(G)| + 2))^{\alpha}\}.

Then Cα\mathcal{C}_{\alpha} is subgraph-closed and nowhere dense. For every sufficiently large even nn, there is a connected nn-vertex graph G∈CαG \in\mathcal{C}_{\alpha} such that, for every correct anonymous radius-one verifier for Even on Cα\mathcal{C}_{\alpha}, every accepting assignment on GG contains a certificate of length at least

1−α3log⁡log⁡n−O(1).\frac{1-\alpha}{3}\log\log n-O(1).

Consequently, certifying Even on Cα\mathcal{C}_{\alpha} has local complexity Θ(log⁡log⁡n)\Theta(\log\log n).

We return to the interval idea from § 4, but use identities between color counts instead of identities between neighborhoods. This lets us change parity by splitting a single vertex, an operation that cannot create a shorter cycle.

For a certificate assignment cc using at most rr distinct strings, identify these strings with [r]:={1,…,r}[r] := \{1,\ldots,r\} and define the profile

mc(v)=(∣{w∈N(v):c(w)=a}∣)a∈[r].\mathbf{m}_{c}(v)=\left(\left|\{w\in N(v):c(w)=a\}\right|\right)_{a\in[r]}.

Thus the local view at vv is determined by c(v)c(v) and mc(v)\mathbf{m}_{c}(v). The same formula defines mc(v)\mathbf{m}_{c}(v) when cc is defined only on a set containing N(v)N(v). These colorings need not be proper.

Lemma 14. Let cc be a certificate assignment on a bipartite graph GG. Suppose that distinct vertices u,v,wu,v,w have the same certificate and

mc(v)=mc(u)+mc(w).\mathbf{m}_{c}(v)=\mathbf{m}_{c}(u)+\mathbf{m}_{c}(w).

There are a simple bipartite graph G′G' of order ∣V(G)∣+1|V(G)|+1 and girth at least that of GG, and a certificate assignment c′c' on G′G', such that every local view in (G′,c′)(G',c') occurs in (G,c)(G,c).

Proof. Replace vv by two vertices v1,v2v_1,v_2, both carrying c(v)c(v). Partition its neighbors within each certificate class so that v1v_1 has profile mc(u)\mathbf{m}_{c}(u) and v2v_2 has profile mc(w)\mathbf{m}_{c}(w). This is possible by the assumed identity. The new vertices imitate uu and ww. Every retained vertex keeps its certificate and the number of its neighbors with each certificate, since any former neighbor of vv is adjacent to exactly one replacement carrying c(v)c(v).

Put v1,v2v_1,v_2 on the same side of the bipartition as vv. Identifying them back into vv maps any new cycle to a closed trail in GG: no edge repeats, since each old edge was assigned to exactly one replacement. The trail contains a cycle of no greater length, so girth does not decrease. The order increases by one. □

For example, profiles (1,1)(1,1), (1,2)(1,2), and (2,3)(2,3) allow the last vertex to be split into two vertices imitating the first two, provided all three carry the same certificate. If splitting disconnects the graph, every component still retains all its local views.

The next lemma supplies such a triple under every small certificate palette. Its property survives adding leaves at a vertex of PP, because none of the old neighborhoods on the YY side changes.

Lemma 15. There is an absolute constant C>1C>1 such that, for all integers r>2r>2 and g≥4g\geq4, there is a connected bipartite graph H=(P∪Y,E)H=(P\cup Y,E) of girth at least gg and order at most 2Cgr2log⁡r2^{C g r^{2}}\log r such that every coloring c:V(H)→[r]c:V(H)\to[r] has distinct vertices u,v,w∈Yu,v,w\in Y with the same color and nonzero profiles satisfying

mc(v)=mc(u)+mc(w).\mathbf{m}_{c}(v)=\mathbf{m}_{c}(u)+\mathbf{m}_{c}(w).

Here is the idea of the proof, deferred to Appendix § 7. An ordered sequence of points gives interval profiles satisfying the exact identity zik=zij+zjk\mathbf{z}_{ik}=\mathbf{z}_{ij}+\mathbf{z}_{jk} for i<j<ki<j<k. For each coloring of PP, a counting argument finds a sequence whose interval profiles all have a reasonable probability of appearing in random subsets. Sampling supplies many vertices with each of these profiles, simultaneously for all colorings, so deleting one set vertex from each short cycle still leaves every profile available. Select a representative for each interval and color its endpoint pair by the representative’s certificate. A monochromatic triangle gives the required three equally certified vertices. No approximation of color frequencies is needed. Figure 5 illustrates how the triangle gives the split.

A monochromatic triangle yields a split

Figure 5. A monochromatic triangle yields a split. The auxiliary edges ijij, jkjk, ikik in (a) have representatives uu, ww, vv with certificate 1 and profiles a\mathbf{a}, b\mathbf{b}, a+b\mathbf{a}+\mathbf{b}. Panels (b,c) show vv’s actual neighborhood: v1v_1 and v2v_2 imitate uu and ww by receiving the two indicated groups. Every old neighbor still sees one vertex with certificate 1. Fills and numeric labels encode certificates. The templates are matched by color counts; their actual neighbors may differ. Unshown vertices and edges are unchanged.

Proof of Lemma 13. Taking a subgraph does not decrease girth or increase order, so CαC_\alpha is subgraph-closed. A depth-ρ\rho minor model of K3K_3 yields a cycle of length at most 6ρ+36\rho+3: join the endpoints of its three connecting edges inside their branch sets by paths of length at most 2ρ2\rho each. These paths have disjoint interiors, since the branch sets are disjoint. For fixed ρ\rho, sufficiently large members of CαC_\alpha therefore exclude this minor. The remaining members have bounded order and exclude a sufficiently large complete minor. This proves nowhere denseness.

Fix a sufficiently large even nn, write L=log⁡nL=\log n, and choose

g=⌈(log⁡(n+3))α⌉,r=⌊L(1−α)/3⌋.g=\left\lceil(\log(n+3))^\alpha\right\rceil,\qquad r=\left\lfloor L^{(1-\alpha)/3}\right\rfloor.

Then g≥4g\ge4 and r≥2r\ge2. Since g=O(Lα)g=O(L^\alpha), Lemma 15 gives a graph HH with

log⁡∣V(H)∣=O(gr2log⁡r)=O(L(2+α)/3log⁡L)=o(L).\log|V(H)|=O(gr^2\log r)=O\left(L^{(2+\alpha)/3}\log L\right)=o(L).

Here the last equality uses α<1\alpha<1. Thus ∣V(H)∣≤n|V(H)|\le\sqrt{n} for large nn. Add leaves at one vertex of PP until the order is exactly nn. The resulting connected graph GnG_n lies in CαC_\alpha and retains the lemma’s profile property.

Suppose an accepting assignment cc on GnG_n uses at most rr distinct certificates. Its restriction to HH gives equally certified vertices u,v,w∈Yu,v,w\in Y with mc(v)=mc(u)+mc(w)\mathbf{m}_{c}(v)=\mathbf{m}_{c}(u)+\mathbf{m}_{c}(w). These are also their profiles in GnG_n, since adding leaves at PP did not change their neighborhoods. Lemma 14 produces an accepted bipartite graph of odd order n+1n+1 and girth at least gg. It has an odd-order component FF. This component is a connected accepted no-instance in the same promised class, since

girth⁡(F)≥g≥(log⁡(∣V(F)∣+2))α\operatorname{girth}(F) \ge g \ge\left(\log(|V(F)| + 2)\right)^{\alpha}

This contradicts soundness on CαC_{\alpha}.

Every accepting assignment thus uses more than rr distinct strings. If their lengths are at most ss, then r+1≤2s+1−1r + 1 \le2^{s+1} - 1. Since r+1>L(1−α)/3r + 1 > L^{(1-\alpha)/3},

s≥log⁡(r+1)−1≥1−α3log⁡log⁡n−1.s \ge\log(r + 1) - 1 \ge\frac{1-\alpha}{3}\log\log n - 1.

The upper bound follows from Theorem 1.

Together with Theorem 1, Lemma 13 implies Theorem 5.

AI disclosure

The writing of this paper and the derivation of its results were assisted by AI agents. We used Claude Code (Anthropic) with the model Claude Opus 5.5, and Codex (OpenAI) with the model GPT-6.1 Sol. The authors reviewed all text and results and take full responsibility for them.

Proof of Lemma 15

Proof. We need three equally colored vertices whose profiles satisfy an additive identity. Intervals provide the identity; a monochromatic triangle will provide the equal colors. The random construction only has to realize enough interval profiles to make this argument survive the removal of short cycles. Throughout the proof, ln⁡\ln denotes the natural logarithm.

Put

D=3r!,η=(D+1)−(r+3),Λ=⌈16η−1ln⁡(2rD)⌉,N=(16ΛD3)g.D = 3r!, \qquad\eta= (D+1)^{-(r+3)}, \qquad\Lambda= \left\lceil16\eta^{-1}\ln(2rD)\right\rceil, \qquad N = (16\Lambda D^3)^g.

Let PP be a fixed set of NN points.

Every coloring has a sequence of likely interval profiles. Fix c:P→[r]c:P\to[r]. For 1≤j≤D1\le j\le D, let qj(z)q_j(\mathbf{z}) be the probability that a uniform jj-element subset of PP has profile z\mathbf{z}. There are at most (D+1)r(D+1)^r possible profiles, since each coordinate is an integer between 0 and DD. Consequently, a random jj-subset has a profile z\mathbf{z} with qj(z)<ηq_j(\mathbf{z})<\eta with probability at most (D+1)rη(D+1)^r\eta.

Now choose a uniform ordered sequence x1,…,xDx_1,\ldots,x_D of distinct points. For each interval (i,j](i,j] of positions, its points form a uniform (j−i)(j-i)-subset of PP. A union bound over fewer than D2D^2 intervals gives

Pr⁡(some interval has a profile of probability <η)≤D2(D+1)rη=D2(D+1)3<1.\Pr(\text{some interval has a profile of probability }<\eta)\le D^2(D+1)^r\eta=\frac{D^2}{(D+1)^3}<1.

Thus we can fix a sequence for which every interval profile zij=∑i<k≤jec(xk)\mathbf{z}_{ij}=\sum_{i<k\le j}\mathbf{e}_{c(x_k)}, with 0≤i<j≤D0\le i<j\le D, has probability at least η\eta under sampling a subset of its own size. Here ea\mathbf{e}_a is the aath unit vector. These nonzero profiles satisfy

zik=zij+zjk(i<j<k).(7)\mathbf{z}_{ik}=\mathbf{z}_{ij}+\mathbf{z}_{jk}\qquad(i<j<k). \tag*{(7)}

Fix one such sequence for each coloring of PP, before making the random graph. The sequence may depend on the coloring; the graph will work for all these choices simultaneously.

Realize the profiles, then remove short cycles. For every 1≤j≤D1\le j\le D, independently sample ΛN\Lambda N uniform jj-element subsets of PP. Represent each sample by a new vertex adjacent to its elements. Repeated subsets give distinct vertices, so this incidence graph is simple and bipartite.

Fix a coloring of PP and one interval profile from its fixed sequence. The number XX of samples realizing that profile is binomial, with mean μ≥ΛNη≥16Nln⁡(2rD)\mu\ge\Lambda N\eta\ge16N\ln(2rD). Exponential Markov gives the elementary tail estimate

Pr⁡(X<N)≤2NE[2−X]≤exp⁡(Nln⁡2−μ/2)≤(2rD)−2N.\Pr(X<N)\le2^N\mathbb{E}[2^{-X}]\le\exp(N\ln2-\mu/2)\le(2rD)^{-2N}.

Indeed, for a binomial variable with MM trials and success probability qq, E[2−X]=(1−q/2)M≤e−Mq/2\mathbb{E}[2^{-X}]=(1-q/2)^M\le e^{-Mq/2}. There are rNr^N colorings and fewer than D2D^2 fixed interval targets per coloring. Hence

Pr⁡(some target has fewer than N copies)≤rND2(2rD)−2N≤(4r)−N<14.\Pr(\text{some target has fewer than }N\text{ copies})\le r^N D^2(2rD)^{-2N}\le(4r)^{-N}<\frac14.

Let ZZ count cycles of length less than gg. A cycle of length 2ℓ2\ell uses ℓ\ell distinct points and ℓ\ell distinct set vertices. There are at most Nℓ(ΛN)ℓN^\ell(\Lambda N)^\ell ordered choices. A sampled set contains two specified distinct points with probability at most 2D2/N22D^2/N^2, and different set vertices were sampled independently. Therefore

EZ≤∑2≤ℓ<g/2(2ΛD3)ℓ≤g(2ΛD3)g=g8gN≤N8.\mathbb{E}Z\le\sum_{2\le\ell<g/2}(2\Lambda D^3)^\ell\le g(2\Lambda D^3)^g=\frac{g}{8g}N\le\frac{N}{8}.

By Markov, Z≤N/2Z \le N/2 with probability at least 3/43/4. Some realization therefore has both properties. Delete one set vertex from each short cycle. At most N/2N/2 vertices are deleted, leaving at least N/2N/2 copies of every fixed interval target for every coloring of PP. All surviving set vertices keep their neighborhoods.

Every component contains a point. Connect the components along a tree by adding paths of length two between points in different components, with fresh internal vertices on the set side. The added edges are bridges. Thus girth is at least gg, and the surviving original set vertices still keep their profiles. The final graph is connected and has at most (DΛ+2)N(D\Lambda+2)N vertices.

A monochromatic triangle gives the split. Every edge coloring of K3r!K_{3r!} with rr colors has a monochromatic triangle; this follows by induction on rr. It is immediate for r=1r=1. For r≥2r \ge2, some vertex has at least 3(r−1)!3(r-1)! neighbors joined to it in one color. Either that color occurs on an edge between those neighbors, completing a triangle, or their complete graph uses at most r−1r-1 colors and induction applies.

Take any coloring of the whole constructed graph with at most rr colors, and use the sequence fixed for its restriction to PP. For every pair $0 \le i < j \le D$, choose a surviving original set vertex yijy_{ij} of profile zijz_{ij}. The representatives can be chosen distinct: fewer than D2D^2 are needed, while every target has at least N/2>D2N/2>D^2 available vertices. Color edge ijij of the complete graph on {0,…,D}\{0,\ldots,D\} by c(yij)c(y_{ij}). The preceding Ramsey bound gives a monochromatic triangle i<j<ki<j<k. Its three representatives have the same color, and (6) gives mc⁡(yik)=mc⁡(yij)+mc⁡(yjk)\operatorname{mc}(y_{ik})=\operatorname{mc}(y_{ij})+\operatorname{mc}(y_{jk}). This is the required triple.

Finally,

log⁡D=O(rlog⁡r),log⁡Λ=O(r2log⁡r),log⁡N=O(gr2log⁡r).\log D=O(r\log r),\qquad\log\Lambda=O(r^{2}\log r),\qquad\log N=O(gr^{2}\log r).

The order bound (DΛ+2)N(D\Lambda+2)N is therefore at most 2Cgr2log⁡r2^{Cgr^{2}\log r} for an absolute constant C≥1C\ge1. □\square

References

  1. [1]Nicolas Bousquet, Laurent Feuilloley, and Sébastien Zeitoun. Complexity landscape for local certification. In 39th International Symposium on Distributed Computing (DISC 2025), volume 356 of Leibniz International Proceedings in Informatics (LIPIcs), pages 18:1–18:21. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025. doi: 10.4230/LIPIcs.DISC.2025.18.DOI
  2. [2]Nicolas Bousquet, Laurent Feuilloley, Jorge Valenzuela, and Sébastien Zeitoun. The local complexity of certifying parity, 2026. DISC 2026; full version.arxiv.org/abs/2606.04934
  3. [3]Yi-Jun Chang, Yi-Xuan Lee, and Meng-Tsung Tsai. Local certification of vertex and edge connectivity, 2026. URL https://arxiv.org/abs/2607.13677.
  4. [4]Panagiotis Cheilaris, Balázs Keszegh, and Dömötör Pálvölgyi. Unique-maximum and conflict-free coloring for hypergraphs and tree graphs. SIAM Journal on Discrete Mathematics, 27(4):1775–1787, 2013. doi: 10.1137/120880471.DOI
  5. [5]Linda Cook, Eun Jung Kim, and Tomáš Masarík. A tight meta-theorem for LOCAL certification of MSO₂ 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.
  6. [6]Tianjiao Dai, Qiancheng Ouyang, and François Pirot. New bounds for odd colourings of graphs. The Electronic Journal of Combinatorics, 31(4):P4.57, 2024. doi: 10.37236/12110.DOI
  7. [7]Guy Even, Zvi Lotker, Dana Ron, and Shakhar Smorodinsky. Conflict-free colorings of simple geometric regions with applications to frequency assignment in cellular networks. SIAM Journal on Computing, 33(1):94–136, 2003. doi: 10.1137/S0097539702431840.DOI
  8. [8]Laurent Feuilloley. Introduction to local certification. Discrete Mathematics & Theoretical Computer Science, 23(3), 2021. doi: 10.46298/dmtcs.6280.DOI
  9. [9]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. doi: 10.1007/s00453-021-00823-w.DOI
  10. [10]Laurent Feuilloley, Nicolas Bousquet, and Théo Pierron. What can be certified compactly? compact local certification of MSO properties in tree-like graphs. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC 2022), pages 131–140. ACM, 2022. doi: 10.1145/3519270.3538416.DOI
  11. [11]Laurent Feuilloley, Josef Erik Sedláček, and Martin Slávik. Proving there is a leader without naming it, 2025. URL https://arxiv.org/abs/2511.15491.
  12. [12]Pierre Fraigniaud, Amos Korman, and David Peleg. Towards a complexity theory for local distributed computing. Journal of the ACM, 60(5):35:1–35:26, 2013. doi: 10.1145/2499228.DOI
  13. [13]Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, and Ioan Todinca. A meta-theorem for distributed certification. Algorithmica, 86(2):585–612, 2024. doi: 10.1007/s00453-023-01185-1.DOI
  14. [14]Mika Göös and Jukka Suomela. Locally checkable proofs in distributed computing. Theory of Computing, 12(19):1–33, 2016. doi: 10.4086/toc.2016.v012a019. URL https://theoryofcomputing.org/articles/v012a019/.DOI
  15. [15]Philip Hall. On representatives of subsets. Journal of the London Mathematical Society, s1-10(1):26–30, 1935. doi: 10.1112/jlms/s1-10.37.26.DOI
  16. [16]Frank Harary, Derbiau Hsu, and Zevi Miller. The biparticity of a graph. Journal of Graph Theory, 1(2):131–133, 1977. doi: 10.1002/jgt.3190010208.DOI
  17. [17]Robert Hickingbotham. Odd colourings, conflict-free colourings and strong colouring numbers. Australasian Journal of Combinatorics, 87(1):160–164, 2023. URL https://ajc.maths.uq.edu.au/pdf/87/ajc_v87_p160.pdf.arxiv.org/abs/2203.10402
  18. [18]Amos Korman, Shay Kutten, and David Peleg. Proof labeling schemes. Distributed Computing, 22(4):215–233, 2010. doi: 10.1007/s00446-010-0095-3.DOI
  19. [19]Jaroslav Nešetřil and Patrice Ossona de Mendez. Sparsity: Graphs, Structures, and Algorithms, volume 28 of Algorithms and Combinatorics. Springer, 2012. doi: 10.1007/978-3-642-27875-4.DOI
  20. [20]János Pach and Gábor Tardos. Conflict-free colourings of graphs and hypergraphs. Combinatorics, Probability and Computing, 18(5):819–834, 2009. doi: 10.1017/S0963548309990290.DOI
  21. [21]Boaz Patt-Shamir and Mor Perry. Proof-labeling schemes: Broadcast, unicast and in between. Theoretical Computer Science, 923:179–195, 2022. doi: 10.1016/j.tcs.2022.05.006.
  22. [22]George Szekeres and Herbert S. Wilf. An inequality for the chromatic number of a graph. Journal of Combinatorial Theory, 4(1):1–3, 1968. doi: 10.1016/S0021-9800(68)80081-X.DOI

Paper details

vlnc:W_jqf4jfbu
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Claude Code, Codex

View statement
Looking for related papers…
Contents