Reductions in local certification

Louis Esperet; S\'ebastien Zeitoun

REVIEW 3 major objections 3 minor 23 references

Reductions in local certification

T0 review · 3 major / 3 minor · reviewed 2026-08-09 · deepseek-v4-flash

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

Pith's one-line read The paper introduces local hardness reductions for local certification and proves a quantitative transfer theorem that turns one lower bound for non-3-colorability into polynomial lower bounds for many classical graph properties.

desk verdict A genuinely useful reduction framework for local certification, with a clean transfer theorem and many applications, but the write-up has slip-ups in the Section 3 counting and a complement mix-up in Section 8 that should be fixed. read the letter →

arxiv 2502.01551 v2 pith:6ISUWYUU submitted 2025-02-03 cs.DC cs.DMcs.DSmath.CO

Louis Esperet , Sébastien Zeitoun This is my paper · ORCID

classification cs.DCcs.DMcs.DSmath.CO MSC 05C1505C8568Q1768Q2568W15

keywords localcertificationprooflabelingschemeshardnessreductionlowerboundsgraphcoloringdistributedalgorithmsdomaticnumberHamiltoniancycles

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper introduces hardness reductions for local certification, the distributed analogue of arguing one property is at least as hard to verify as another. Its central theorem transfers certificate size bounds: if a property $P'$ can be certified with certificates of size $s(n)$, and a local reduction from $P$ to $P'$ has local expansion $\alpha$ and global expansion $\beta$, then $P$ can be certified with certificates of size $O(\alpha(n) \cdot s(\beta(n)))$. Starting from the known quadratic lower bound for non-3-colorability, the paper derives polynomial lower bounds for non-$k$-colorability, bounded domatic number, absence of cubic subgraphs, acyclic partition, monochromatic triangles, non-Hamiltonicity, and chromatic index $\Delta+1$, many in bounded-degree classes. It also shows the transfer is quantitative: reductions with small local expansion preserve strong lower bounds, while large expansion degrades them. The framework answers a gap in the area, where lower-bound proofs had previously been largely problem-specific.

What carries the argument

The load-bearing mechanism is the local reduction $f_{P,P'}$ with local expansion $\alpha$ and global expansion $\beta$: a graph transformation preserving the property, with six conditions (R1)-(R3f) that make the verification simulation airtight. Conditions (R3d) and (R3e) are the core of soundness: the set of source vertices that hold a given certificate must be connected so that the certificate is globally consistent, and the closed neighborhood of any vertex being simulated must be covered by certificates held by the simulating vertex and its neighbors. The proof of the transfer theorem constructs, from any certificate assignment on the source, a certificate assignment on the target by reading the common table entries; the verifier of $P'$ then accepts everywhere on $G'$, proving $G$ satisfies $P$.

What would settle it

Check that construction on the smallest nontrivial index sets: if two distinct choices $A,B$ produce a 3-colorable graph even when $A \cap \bar{B} \neq \emptyset$, or if the special-vertex subgraph changes with $A,B$, the pigeonhole step used in Theorems 3.2 and 3.3 fails. Alternatively, run one of the Section 5 reductions on a small non-3-colorable graph and look for a certificate assignment that makes every vertex of the target property's verifier accept on the transformed graph; such an assignment would falsify soundness and undo the transferred lower bound.

Watch

Extended reading notes

Core claim

The central claim is that local reductions, defined by six conditions, transfer certification lower bounds from a base property to a target property without redoing the lower-bound proof. For each vertex $u$ of the original graph $G$, the reduction asks for a small set $C_u$ of vertices of the transformed graph $G'$ whose certificates $u$ will receive, and a subset $V_u \subseteq C_u$ of vertices whose local verification $u$ can simulate; the conditions ensure that certificates for the same transformed vertex agree across all holders, and that every neighbor of a vertex in $V_u$ has its certificate available within $u$'s neighborhood. The proof of the transfer theorem then pastes the certification scheme of the target property into tables and runs the target verifier locally in the source graph. With the base lower bound for non-3-colorability as the root, the paper obtains the lower bounds of Table 1, including bounded-degree variants, a 3-SAT version, and a bounded-degree relaxation that lowers the degree threshold for non-$k$-colorability. It also proves a limit of the method by showing a coNP-hard property with only logarithmic local complexity, and gives reductions for polynomial-time properties such as forbidden induced subgraphs.

Load-bearing premise

Every transferred lower bound rests on the base construction for non-3-colorability having the four structural properties listed in Section 3-especially that the built graph is 3-colorable exactly when two index sets intersect and that the subgraph induced by the special vertices is independent of the index sets.

Editorial extensions

If this is right

Any property that can be locally reduced from non-3-colorability inherits a polynomial certificate lower bound, so the problems in Table 1 are all hard to certify locally even when restricted to bounded-degree graphs.
The quantitative form of the transfer gives a design target: a reduction with local expansion $O(n^\delta)$ and global expansion $O(n^\gamma)$ yields a lower bound of about $n^{(2-\delta)/\gamma}/\log n$ from the quadratic base, so keeping both expansions small is what preserves strong bounds.
The 3-SAT variant means future reductions can be written from satisfiability problems rather than graph coloring, which is often more convenient and gives the same lower bounds for Hamiltonian cycle and edge-coloring.
The framework also transfers upper bounds: an efficient certification scheme for the target property would produce an efficient scheme for the source, giving a reusable route for positive results.
The logarithmic complexity example for a coNP-hard property sets a boundary: polynomial local complexity is not implied by coNP-hardness alone, so the reductions, not the decision complexity, are doing the work.

Reading between the lines

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

[Editorial inference] The reduction conditions are likely to be reusable as a checklist for turning classical NP-hardness reductions into local lower-bound proofs; the open cases named in Section 8 (bandwidth, disk graphs, unit-disk graphs) are natural candidates where a sufficiently local reduction would settle the question.
[Editorial inference] Because the definition is symmetric under complementation, one could try to use it for upper bounds: if a target property has a cheap certification scheme, then any property that reduces to it inherits cheap certificates, which may be a convenient way to prove logarithmic upper bounds without constructing schemes from scratch.
[Editorial inference] The bounded-degree relaxation in Section 7 suggests that locality is not a single threshold: allowing dependence on a constant-radius ball rather than the immediate neighborhood still preserves the transfer, which may apply to other problems where natural gadgets are two-local but not one-local.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

Two things you should know. First, this paper delivers a genuinely new tool for local certification: a notion of local reduction with a transfer theorem, and uses it to get polynomial lower bounds for over a dozen classical properties, several optimal up to polylogs. Second, the write-up has two correctness issues that need fixing before I'd rely on it as printed: the counting in Section 3 has sizes that don't support the pigeonhole bounds, and Section 8's example certifies the complement of the property it actually defines.

The core is solid. The local reduction definition (local expansion α, global expansion β) is a sensible formalization, and Theorem 5.2—certificate size O(α(n)·s(β(n)))—is proved with care. The conditions (R3a)-(R3f) are reasonable, and the applications are not routine: the domatic number, cubic subgraph, acyclic partition, monochromatic triangle, non-Hamiltonicity, and chromatic index lower bounds all follow from the framework with real gadget work. The most intricate gadget proofs are spelled out.

Now the soft spots, in proportion. The stress-test note is correct: the sizes as printed in Section 3 don't make the pigeonhole arguments work. The text says G_{A,B} has n=Θ(2^k) vertices, then uses 2^{(2k)^2}=2^{Ω(n^2)} choices—that needs n=Θ(k). Similarly, H_{A,B} is said to have n=Θ(2^{2k}) but the proof needs 2^{Ω(n)} choices, which requires n=Θ(k^2). And the planar bound needs n=Θ(k^4). These are almost certainly typos: replace the exponential sizes with the polynomial ones and the arguments go through as written. As printed, the lower bounds in Table 1 are not justified. The authors need to correct this before publication; a referee should insist.

The Section 8 issue is a genuine mistake, not a typo. The property P is defined existentially (there exists a vertex with a partition of neighbors), and the O(log n) scheme described actually certifies the complement (no such vertex). The claim as written confuses a coNP-complete problem with its NP-complete complement. Peripheral, but it should be fixed.

The reliance on Göös-Suomela is appropriate; the base lower bound is cited, not re-derived. The citation pattern looks clean. I disagree with the reader's high confidence on soundness as printed, but I agree the framework is sound after the typo corrections.

Who this is for: anyone working on local certification or distributed verification. It deserves a serious referee—the central idea is important and, modulo the fixes, correct. Recommendation: send to review, with a request to fix the size bounds in Section 3 and the complement in Section 8.

Referee Report

3 major / 3 minor

Summary. The paper introduces a formal notion of local hardness reduction between graph properties in the context of local certification, proves a transfer theorem showing that a certification scheme for the target property yields one for the source property, and uses this to derive polynomial lower bounds for several classical coNP-hard properties by reducing from non-3-colorability. A variant for reductions from 3-SAT is also given, with applications to non-Hamiltonicity and chromatic index. The main theoretical contribution is Theorem 5.2, and the paper includes detailed gadget constructions for the applications.

Significance. If the technical issues identified below are resolved, the paper would provide a valuable unifying framework for lower bounds in local certification, analogous to reductions in classical complexity. The central transfer theorem is clean and the applications cover a diverse set of properties, with several gadget proofs spelled out in detail. The paper also honestly identifies limitations, such as the coNP-hard problem with logarithmic complexity in Section 8 and the open problems on bandwidth and disk graphs. However, the current manuscript contains load-bearing inconsistencies in the base counting argument of Section 3 and in the statements of the main corollaries, so the results are not yet fully supported as written.

major comments (3)

[Section 3, Theorems 3.1-3.3] The parameterization of the Göös-Suomela construction is inconsistent as printed. With I={1,...,2k} and A,B subsets of I×I, the number of choices for A is 2^{(2k)^2}. If G_{A,B} has n=Theta(2^k) vertices, then (2k)^2 = Theta((log n)^2), so the number of choices is 2^{Theta((log n)^2)}, not 2^{Omega(n^2)} as used in the proof of Theorem 3.1. Similarly, in Theorem 3.2 the proof states H_{A,B} has n=Theta(2^{2k}) vertices and then uses 2^{(2k)^2}=2^{Omega(n)} choices, which is false: with n=Theta(2^{2k}), (2k)^2=Theta((log n)^2). In Theorem 3.3 the same type of mismatch occurs: n=O(2^{4k}) does not give 2^{Omega(sqrt n)} choices. These counting steps are the base of every transferred lower bound in the paper, so the correct size of G_{A,B} must be stated and the pigeonhole bounds re-derived from [15].
[Section 3, Theorem 3.2] The claim that the special vertex sets S_A and S_B remain of size O(log n) after applying the degree-reduction f is not justified by the properties listed in Section 3. The proof says this follows from item (3), but item (3) only bounds the number of edges between S_A and S_B. The size of f(S_A) depends on the total degree of the vertices in S_A inside V_A, which is not bounded by the stated properties. Moreover, item (3) says there are at most O(k) cross edges, while the proof of Theorem 3.2 uses O(log n) cross edges; these two statements are compatible only under one of the conflicting size conventions. The authors need an explicit bound on the total degree of the special vertices in G_{A,B}, or a different argument that the special vertices remain O(log n) after the reduction.
[Corollaries 5.3 and 6.4] The statements of Corollary 5.3 and Corollary 6.4 are false as written. Corollary 5.3 claims that a local reduction from k-colorability to P implies a lower bound for P. But k-colorability has O(log n) local complexity, and the identity reduction from k-colorability to itself satisfies the hypotheses with alpha=beta=1, so the conclusion would give Omega(n^2/log n), a contradiction. The proof of the corollary actually uses a reduction from non-k-colorability to P, not from k-colorability. The statement must be corrected to say either that a reduction from non-k-colorability to P implies a lower bound for P, or that a reduction from k-colorability to P implies a lower bound for the complement of P. The same issue applies to Corollary 6.4 for reductions from 3-SAT. The applications in Sections 5 and 6 construct reductions from the positive properties (e.g., (k+1)-colorability, 3-colorability) to positive target properties, while the stated lower bounds concern the complements; the authors must explicitly invoke the complement symmetry of Remark 5.1 to make the logical chain valid.

minor comments (3)

[Section 7, Theorem 7.1] In the construction after the display defining the new endpoints, the text says 'for each vertex u, we detach the edges of u incident to its ceil(sqrt k) neighbors having smallest identifiers', but the formal definition detaches the edges to the k neighbors of smallest identifier. The informal sentence should be corrected to match the formal construction.
[Remark 5.1] The displayed statement of the symmetry property has garbled overlines: it reads 'there exists a local reduction from P to P' if and only if there exists a local reduction from P to P''. This should read 'from P to P' if and only if from complement of P to complement of P''. Since the applications rely on this symmetry, the corrected statement should be printed explicitly.
[Section 6.1] In the verification that the non-Hamiltonicity reduction satisfies the locality conditions, condition (S3f) is asserted to follow from the definitions, but this is not immediately obvious because C_{x_i} includes entry/exit nodes and first/last row vertices of all variables. Please provide a short explicit argument that these sets and the relevant local subgraphs depend only on the clauses containing x_i.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: Theorem 5.2 is proved from the local-reduction definitions and the transferred lower bounds bottom out in the external Göös–Suomela [15] construction.

full rationale

The central claim, Theorem 5.2, is a direct simulation argument: if P' has certificates of size s and P reduces locally to P' with expansion α/β, the paper constructs P-certificates of size O(α(n)s(β(n))). The proof uses only the local-reduction conditions (R1)–(R3f) and the given P' scheme; it does not assume the P lower bound it transfers. Every lower bound in Table 1 is then obtained by applying this theorem (or Corollary 5.3) to the Göös–Suomela non-3-colorability lower bound, which is cited as an external result ([15]) and not re-derived in this paper. The paper explicitly acknowledges that it does not fully reproduce that construction ('The full description of the construction in [15] takes over 6 pages ... we do not describe it completely here'), but reliance on an external cited result is not circularity. The self-citations do not create circularity: [2] is used only for an auxiliary identifier-renaming lemma in the proof of Theorem 5.2, and [1] is used in the final illustrative section for an already-known H-freeness lower bound; neither supplies the main lower-bound content nor is equivalent to the paper's conclusions. The Section 3 counting concern (n=Θ(2^k) printed while 2^{(2k)^2}=2^{Ω(n^2)} is claimed) is a correctness/presentation issue in transcribing the external construction, not a circular reduction: the pigeonhole counting is inherited from [15], not from the paper's own input. No self-definitional, fitted-input, self-citation-load-bearing, or imported-uniqueness circularity is present.

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

The central theorem is proved directly from the definitions. The main external inputs are the Göös-Suomela lower bound and standard NP-completeness reductions. No free parameters are fitted; local and global expansion functions are part of the reduction definition, not posteriori choices.

assumptions (4)

domain assumption Göös-Suomela lower bound: non-3-colorability has local complexity Ω(n^2/log n), with the structural properties (1)-(4) of the graph GA,B.
Invoked in Section 3 as Theorem 3.1 and used as the base for all later reductions. The paper does not prove this result; it cites [15].
domain assumption Standard NP-completeness reductions used for applications: Garey-Johnson [14], Sipser [21], Holyer [17], Emden-Weinert et al. [6], Molloy-Reed [18].
The correctness of several applications relies on the existence and correctness of these reductions, which are cited rather than proved in full.
domain assumption The local certification model with unique identifiers in {1,...,poly(n)} and computationally unbounded verifiers.
Section 2.2 defines the model; all results are stated within it.
domain assumption Graphs are simple, loopless, undirected, and connected.
Section 2.1 assumes this; it is used in several proofs, e.g., Theorem 5.4 and Theorem 5.6.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Reductions in local certification." pith.science (2026). https://pith.science/paper/6ISUWYUU

@misc{pith2026250201551,
  author       = {Pith},
  title        = {Pith review of: Reductions in local certification},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6ISUWYUU}},
  note         = {Machine review of arXiv:2502.01551}
}

abstract

Local certification is a topic originating from distributed computing, where a prover tries to convince the vertices of a graph $G$ that $G$ satisfies some property $\mathcal{P}$. To convince the vertices, the prover gives a small piece of information, called certificate, to each vertex, and the vertices then decide whether the property $\mathcal{P}$ is satisfied by just looking at their certificate and the certificates of their neighbors. When studying a property $\mathcal{P}$ in the perspective of local certification, the aim is to find the optimal size of the certificates needed to certify $\mathcal{P}$, which can be viewed a measure of the local complexity of $\mathcal{P}$. A certification scheme is considered to be efficient if the size of the certificates is polylogarithmic in the number of vertices. While there have been a number of meta-theorems providing efficient certification schemes for general graph classes, the proofs of the lower bounds on the size of the certificates are usually very problem-dependent. In this work, we introduce a notion of hardness reduction in local certification, and show that we can transfer a lower bound on the certificates for a property $\mathcal{P}$ to a lower bound for another property $\mathcal{P}'$, via a (local) hardness reduction from $\mathcal{P}$ to $\mathcal{P}'$. We then give a number of applications in which we obtain polynomial lower bounds for many classical properties using such reductions.

Figures

Figures reproduced from arXiv: 2502.01551 by the authors.

**Figure 1.** The graph Gu. For any integer k, and any two subsets A ⊆ I × I and B ⊆ I × I (where I = {1, . . . , 2 k}), we consider the graph GA,B of Göös and Suomela [15] introduced above, and we let HA,B = f(GA,B). Note that HA,B contains n = Θ(22k ) vertices, and moreover: (1) HA,B can be partitioned into two parts VA (such that HA,B[VA] depends only on A) and VB (such that HA,B[VB] depends only on B). (2) VA contains a set S… view at source ↗

**Figure 2.** Drawing HA,B in the plane before the addition of uncrossing gadgets. We then use uncrossing gadgets introduced in [14] (see [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗

**Figure 3.** Uncrossing gadgets. of size o(n 1/2/ log2 n) then the total number of bits of certificates assigned to the special vertices of P ′ A,A¯ is o(n 1/2 ) and thus there are two distinct sets A, B such that the certificates of P ′ A,A¯ and P ′ B,B¯ agree on their special vertices. We then obtain a contradiction using the same argument as above. □ Remark 3.4. A closer inspection of the construction of Göös and Suomela [15]… view at source ↗

Figures from the paper (19 more)

**Figure 4.** Figure 4: The graph G′ when k = 4 and G is a cycle of length 4. The thick double edges between the cliques represent the antimatchings. Theorem 4.1. For any fixed k ⩾ 3, non-k-colorability has local complexity at least Ω(n 2/ log n) in general graphs, and at least Ω(n/ log n) i…

**Figure 5.** Figure 5: The reduction from (k+1)-colorability to domatic number at least k + 1. The clique Kuv contains k − 1 vertices. The identifier of each vertex in G′ indicates if it is a vertex of G (and which one), or a vertex in a clique Kuv added for an edge uv of G (together with th…

**Figure 6.** Figure 6: Some graphs G and G′ = f(k + 1)-col,P(G), with k = 2. Let us show that G admits a proper (k + 1)-coloring if and only if the domatic number of G′ is at least k + 1. Assume that G is (k + 1)-colorable. Then, we define a (k + 1)-coloring of the vertices of G′ in the foll…

**Figure 7.** Figure 7: The transformation from a proper (k + 1)-coloring of G to a partition into k + 1 dominating sets of G′ = f(k+1)-col,P(G), with k = 2. In the drawing of G′ , the colors correspond to the parts of the partition. Let us show that the conditions of the definition of local …

**Figure 8.** Figure 8: A linking-component with four outputs, and its symbolic representation. The red vertex is the root. The white vertices are the terminals. The yellow vertices are the internal vertices (and do not appear in the symbolic representation). Then, we define an tag, represent…

**Figure 9.** Figure 9: A tag, and its symbolic representation. The red vertex is the root. The graph G′ = f3-col,P(G) is constructed as follows. For every vertex u ∈ V (G) of degree d (with d ∈ {1, 2, 3, 4}), we create one tag and three linking-components with d outputs associated to u, and …

**Figure 10.** Figure 10: The graph G′ = f3-col,P(G), where G is a path on three vertices. The red vertices are the roots. The thick edges are the connecting edges. The colors of the linking components represent their number. We already know that all the internal vertices of the tags and linki…

**Figure 11.** Figure 11: The construction of G0. T 1 u T 2 u T 3 u T 123 u [PITH_FULL_IMAGE:figures/full_fig_p022_11.png]

**Figure 12.** Figure 12: Some of the edges in the construction of G1. Finally, for every vertex u ∈ G, we define Vu and Cu as being both equal to the set containing the vertices in T 0 u , euv, T i u , T ij u , T 123 u , T i uv for some i, j ∈ {1, 2, 3} and v ∈ N(u). Since G has maximum degre…

**Figure 13.** Figure 13: (top) The main color of uvw and the color of st are the same; (bottom) A coloring of K5 without monochromatic triangle completing the previous one. By Lemma 5.12, in the 2-edge-coloring of G′ without monochromatic triangles, for every uv ∈ E(G), since the union of T 0…

**Figure 14.** Figure 14: The graph f ∗ P (φ). There are n rows (one per variable). The edges between the vertices corresponding to the clauses and the rest of the graph are not represented here. The green vertices are those in Vx1 (assuming that x1 or its negation belongs to C1 and C2, but no…

**Figure 15.** Figure 15: The connection between the nodes corresponding to clauses and the rest of the graph. On this example, x1 appears in C1, x1 appears in C2 [PITH_FULL_IMAGE:figures/full_fig_p028_15.png]

**Figure 16.** Figure 16: An inverting component and its symbolic representation. In an edge-coloring, a pair of edges is said to be true (resp. false) if it is colored with the same colors (resp. with different colors). In any proper 3-edge-coloring of an inverting component, exactly one of t…

**Figure 17.** Figure 17: A variable-setting component with four outputs. 1 2 3 [PITH_FULL_IMAGE:figures/full_fig_p030_17.png]

**Figure 18.** Figure 18: A satisfaction-testing component. the clauses containing xj1 or its negation by lexicographic order of the variables appearing inside, Cj is the ℓ-th. We connect the ℓ-th output of the variable-setting component of xj1 to the input 1 of the satisfaction-testing compon…

**Figure 19.** Figure 19: An example of the operation performed in the reduction of [6], with k = 4. The degree of u decreased by one after this operation. First, recall that by Theorem 4.1, at least Ω(n/ log n) bits are necessary to certify non-k-colorability in graphs of maximum degree 5k−4…

**Figure 20.** Figure 20: The strong product of a path and a K2. an Ω(n) lower bound for the local complexity of H′ -freeness where H′ is the graph depicted in [PITH_FULL_IMAGE:figures/full_fig_p035_20.png]

**Figure 21.** Figure 21: A comb of length 7. If f consists in adding a pending path of length t to every vertex, if i, j are two integers such that i + j ⩾ 6, it can easily be checked that G contains no path of length i + j + 1 if and only if f(G) contains no claw with a central vertex and th…

**Figure 22.** Figure 22: The claw with branches of size (3, 5, 7). Finally, let us mention some problems for which we were not able to apply our reduction framework. Let G be an n-vertex graph, and let Sn denote the set of all bijections V (G) → {1, . . . , n}. The bandwidth of G, denoted by …

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

23 extracted references · 22 canonical work pages

[15]

Locally checkable proofs in distributed computing.Theory Comput., 12(1):1–33, 2016

Mika Göös and Jukka Suomela. Locally checkable proofs in distributed computing.Theory Comput., 12(1):1–33, 2016

work page 2016
[1]

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

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

arXiv 2024
[2]

Renaming in distributed certification

Nicolas Bousquet, Louis Esperet, Laurent Feuilloley, and Sébastien Zeitoun. Renaming in distributed certification. CoRR, abs/2409.15404, 2024

work page arXiv 2024
[3]

Kirkpatrick

Heinz Breu and David G. Kirkpatrick. Unit disk graph recognition is np-hard.Comput. Geom., 9(1-2):3–24, 1998

work page 1998
[4]

Local certification of geometric graph classes

Oscar Defrain, Louis Esperet, Aurélie Lagoutte, Pat Morin, and Jean-Florent Raymond. Local certification of geometric graph classes. In Rastislav Královic and Antonín Kucera, editors, 49th International Symposium on Mathematical Foundations of Computer Science, MFCS 2024, August 26-30, 2024, Bratislava, Slovakia , volume 306 of LIPIcs, pages 48:1–48:14. S...

work page 2024
[5]

On the power of the congested clique model

Andrew Drucker, Fabian Kuhn, and Rotem Oshman. On the power of the congested clique model. In Magnús M. Halldórsson and Shlomi Dolev, editors,ACM Symposium on Principles of Distributed Computing, PODC ’14, Paris, France, July 15-18, 2014 , pages 367–376. ACM, 2014

work page 2014
[6]

Uniquely colourable graphs and the hardness of colouring graphs of large girth.Comb

Thomas Emden-Weinert, Stefan Hougardy, and Bernd Kreuter. Uniquely colourable graphs and the hardness of colouring graphs of large girth.Comb. Probab. Comput. , 7(4):375–386, 1998

work page 1998
[7]

Local certification of graphs on surfaces.Theoretical Computer Science, 909:68–75, 2022

Louis Esperet and Benjamin Lévêque. Local certification of graphs on surfaces.Theoretical Computer Science, 909:68–75, 2022

work page 2022

Show all 23 references

[8]

Introduction to local certification.Discret

Laurent Feuilloley. Introduction to local certification.Discret. Math. Theor. Comput. Sci. , 23(3), 2021

2021
[9]

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

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 Com- puting, Salerno...

2022
[10]

Compact distributed certification of planar graphs.Algorithmica, 83(7):2215– 2244, 2021

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

2021
[11]

Discrete Applied Mathematics, 325:9–36, 2023

Laurent Feuilloley, Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, Éric Rémila, and IoanTodinca.Localcertificationofgraphswithboundedgenus. Discrete Applied Mathematics, 325:9–36, 2023. REDUCTIONS IN LOCAL CERTIFICATION 37

2023
[12]

Distributed certification for classes of dense graphs

Pierre Fraigniaud, Frédéric Mazoit, Pedro Montealegre, Ivan Rapaport, and Ioan Todinca. Distributed certification for classes of dense graphs. In Rotem Oshman, editor,37th Inter- national Symposium on Distributed Computing, DISC 2023, October 10-12, 2023, L’Aquila, Italy, volu...

2023
[13]

A meta-theorem for distributed certification

Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, and Ioan Todinca. A meta-theorem for distributed certification. In Merav Parter, editor,Structural Information and Communication Complexity - 29th International Colloquium, SIROCCO 2022, Paderborn, Germany, June 27- 29, 2022...

2022
[14]

Garey, David S

Michael R. Garey, David S. Johnson, and Larry J. Stockmeyer. Some simplified NP-complete graph problems. Theor. Comput. Sci. , 1(3):237–267, 1976

1976
[16]

Representing graphs by disks and balls (a survey of recognition-complexity results)

Petr Hlinený and Jan Kratochvíl. Representing graphs by disks and balls (a survey of recognition-complexity results). Discret. Math., 229(1-3):101–124, 2001

2001
[17]

The NP-completeness of edge-coloring.SIAM J

Ian Holyer. The NP-completeness of edge-coloring.SIAM J. Comput. , 10(4):718–720, 1981

1981
[18]

Colouring graphs when the number of colours is almost the maximum degree

Michael Molloy and Bruce Reed. Colouring graphs when the number of colours is almost the maximum degree. J. Comb. Theory, Ser. B , 109:134–195, 2014

2014
[19]

The power of distributed verifiers in interactive proofs

Moni Naor, Merav Parter, and Eylon Yogev. The power of distributed verifiers in interactive proofs. In Shuchi Chawla, editor,Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020 , pages1096–115.SIAM, 2020

2020
[20]

Papadimitriou

Christos H. Papadimitriou. The np-completeness of the bandwidth minimization problem. Computing, 16(3):263–270, 1976

1976
[21]

Introduction to the theory of computation

Michael Sipser. Introduction to the theory of computation . PWS Publishing Company, 1997

1997
[22]

Iain A. Stewart. Deciding whether a planar graph has a cubic subgraph is NP-complete. Discret. Math., 126(1-3):349–357, 1994

1994
[23]

Iain A. Stewart. On locating cubic subgraphs in bounded-degree connected bipartite graphs. Discret. Math., 163(1-3):319–324, 1997. (L. Esperet)Univ. Grenoble Alpes, CNRS, Laboratoire G-SCOP, Grenoble, France Email address: louis.esperet@grenoble-inp.fr (S. Zeitoun) CNRS, INSA ...

1997

Pith tools

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

[1] [15]

Locally checkable proofs in distributed computing.Theory Comput., 12(1):1–33, 2016

Mika Göös and Jukka Suomela. Locally checkable proofs in distributed computing.Theory Comput., 12(1):1–33, 2016

work page 2016

[2] [1]

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

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

arXiv 2024

[3] [2]

Renaming in distributed certification

Nicolas Bousquet, Louis Esperet, Laurent Feuilloley, and Sébastien Zeitoun. Renaming in distributed certification. CoRR, abs/2409.15404, 2024

work page arXiv 2024

[4] [3]

Kirkpatrick

Heinz Breu and David G. Kirkpatrick. Unit disk graph recognition is np-hard.Comput. Geom., 9(1-2):3–24, 1998

work page 1998

[5] [4]

Local certification of geometric graph classes

Oscar Defrain, Louis Esperet, Aurélie Lagoutte, Pat Morin, and Jean-Florent Raymond. Local certification of geometric graph classes. In Rastislav Královic and Antonín Kucera, editors, 49th International Symposium on Mathematical Foundations of Computer Science, MFCS 2024, August 26-30, 2024, Bratislava, Slovakia , volume 306 of LIPIcs, pages 48:1–48:14. S...

work page 2024

[6] [5]

On the power of the congested clique model

Andrew Drucker, Fabian Kuhn, and Rotem Oshman. On the power of the congested clique model. In Magnús M. Halldórsson and Shlomi Dolev, editors,ACM Symposium on Principles of Distributed Computing, PODC ’14, Paris, France, July 15-18, 2014 , pages 367–376. ACM, 2014

work page 2014

[7] [6]

Uniquely colourable graphs and the hardness of colouring graphs of large girth.Comb

Thomas Emden-Weinert, Stefan Hougardy, and Bernd Kreuter. Uniquely colourable graphs and the hardness of colouring graphs of large girth.Comb. Probab. Comput. , 7(4):375–386, 1998

work page 1998

[8] [7]

Local certification of graphs on surfaces.Theoretical Computer Science, 909:68–75, 2022

Louis Esperet and Benjamin Lévêque. Local certification of graphs on surfaces.Theoretical Computer Science, 909:68–75, 2022

work page 2022