{"id":"1e7340d2-f88b-40a2-b531-f49e09a88d97","arxiv_id":"2502.01551","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A new notion of local hardness reduction lets lower bounds on local certification certificate size be transferred between graph properties, yielding polynomial lower bounds for many coNP-hard problems.","lead":"This paper introduces a reduction framework for local certification, allowing lower bounds on certificate sizes to be transferred from one graph property to another. It proves polynomial lower bounds for many classical graph properties, including non-k-colorability, non-Hamiltonicity, and chromatic index.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The base Göös–Suomela counting in §3 is internally inconsistent: the stated vertex counts n=Θ(2^k) and n=Θ(2^{2k}) do not give the 2^{Ω(n^2)}, 2^{Ω(n)}, and 2^{Ω(√n)} pigeonhole bounds used for every transferred lower bound.","rationale":"The reader's weakest assumption points at the Göös–Suomela construction and the size relationships involving k and the vertex count, which is the right area. My stress-test makes the issue more concrete: the text's own displayed sizes contradict the pigeonhole equations used in the proofs of Theorems 3.1–3.3. This is not a question of external consensus but of internal consistency of the counting argument. If the printed n=Θ(2^k) and n=Θ(2^{2k}) are taken literally, the number of A-subsets is 2^{Θ((log n)^2)}, which is far too small to force a collision against 2^{o(n^2)} or 2^{o(n)} certificate assignments. The intended construction in [15] may well have the polynomial-in-k size that makes the counting valid, in which case the paper's framework and transfer theorem remain sound and only the exposition needs correcting. Because the concern is checkable and does not by itself refute the central ideas, I do not move the reader's conditional verdict; I would require the counts to be verified before accepting the applications as stated. The Section 8 sign issue noted by the reader is real but peripheral, and I focus on the base-counting concern because it is load-bearing for the entire lower-bound machinery.","tokens_in":30761,"tokens_out":18647,"duration_ms":167062,"concrete_test":"Re-derive from [15] the exact vertex count n(k), special-vertex count s(k), and number of edges between S_A and S_B in G_{A,B}; then recompute the vertex count after the degree-4 gadget f of Theorem 3.2 and after the planar uncrossing of Theorem 3.3. Check that 2^{(2k)^2} is really 2^{Ω(n^2)} in Theorem 3.1, 2^{Ω(n)} in Theorem 3.2, and 2^{Ω(√n)} in Theorem 3.3 with these actual sizes, and that the special vertices compared in the pigeonhole step still carry O(log n) certificates total. If one of these count relationships fails, the base lower bounds and all transferred bounds need revision; if they hold, the apparent 2^k in the text is only a typo and the framework stands.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Every application in the paper is a corollary of Theorems 3.2 and 3.3, and those theorems are the pigeonhole argument applied to the Göös–Suomela graphs G_{A,B}. As printed in Section 3, I={1,...,2k}, A,B⊆I×I, and G_{A,B} has n=Θ(2^k) vertices; Theorem 3.2 then sets H_{A,B}=f(G_{A,B}) and says H has n=Θ(2^{2k}) vertices. But the proof needs the number of choices of A, 2^{(2k)^2}, to be 2^{Ω(n^2)} in Theorem 3.1, 2^{Ω(n)} in Theorem 3.2, and 2^{Ω(√n)} in Theorem 3.3. With the printed sizes, (2k)^2 is Θ((log n)^2) in the first case and also Θ((log n)^2) in the second and third cases, none of which matches the claimed exponential-in-n count. The counting only works if the actual vertex count is polynomial in k, at least before the degree reduction, and if the O(log n) compared special vertices remain O(log n) after f and after planar uncrossing. If the printed sizes are literal, the pigeonhole step collapses and with it every lower bound in Table 1; if they are typographical errors, the real sizes must be re-derived from [15] before Theorem 5.2 can transfer anything. This is the single load-bearing assumption of the paper.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":31044,"tokens_out":36067,"duration_ms":311629,"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":[{"comment":"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":"Section 3, Theorems 3.1-3.3"},{"comment":"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.","section":"Section 3, Theorem 3.2"},{"comment":"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.","section":"Corollaries 5.3 and 6.4"}],"minor_comments":[{"comment":"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.","section":"Section 7, Theorem 7.1"},{"comment":"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":"Remark 5.1"},{"comment":"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.","section":"Section 6.1"}],"recommendation":"major_revision","confidential_remarks":"The core idea of the paper is attractive and the transfer theorem appears sound, but the two main issues are load-bearing: the Section 3 counting must be corrected against the actual Göös-Suomela construction, and the statements of Corollaries 5.3 and 6.4 must be fixed so that the applications are logically valid. Given that these are fixable within the scope of the paper, I recommend major revision rather than rejection. It would also be helpful if the authors verified the size of the special vertices after the degree reduction against the original construction."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThe 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.\n\nNow 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.\n\nThe 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.\n\nThe 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.\n\nWho 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.","headline":"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.","tokens_in":31606,"tokens_out":10037,"would_cite":true,"duration_ms":81008,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C15","05C85","68Q17","68Q25","68W15"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["local certification","proof labeling schemes","hardness reduction","lower bounds","graph coloring","distributed graph algorithms","domatic number","Hamiltonian cycles"],"falsifier":"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.","tokens_in":30510,"feed_emoji":"📐","tokens_out":9461,"duration_ms":75267,"temperature":0.7,"pith_summary":"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.","feed_headline":"Local reductions turn one lower bound into many","feed_subtitle":"A transfer theorem carries certificate lower bounds from 3-coloring to Hamiltonian cycles and other classical problems.","key_machinery":"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$.","core_discovery":"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.","pith_inferences":["[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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the base lower bound for non-3-colorability and the graph construction with the four structural properties used in every pigeonhole argument.","marker":"[15]"},{"why":"Provides the classical bounded-degree and uncrossing gadgets that preserve 3-colorability in the degree-4 and planar variants.","marker":"[14]"},{"why":"Supplies the 3-SAT-to-Hamiltonian-cycle reduction used to prove the non-Hamiltonicity lower bound.","marker":"[21]"},{"why":"Supplies the 3-SAT-to-edge-coloring reduction used to prove the chromatic-index lower bound.","marker":"[17]"},{"why":"Supplies the degree-reducing operation used to push the k-coloring lower bound to maximum degree $k+\\lceil\\sqrt{k}\\rceil-1$.","marker":"[6]"},{"why":"Provides the structural theorem on k-colorability of near-maximum-degree graphs that gives the matching logarithmic upper bound at degree $k+\\lceil\\sqrt{k}\\rceil-3$.","marker":"[18]"},{"why":"Supplies the identifier-renaming technique that lets the transfer theorem assume identifiers in $\\{1,\\ldots,n\\}$ at $O(\\log n)$ extra cost.","marker":"[2]"}],"fun_headline_variants":["Local reductions transfer lower bounds across properties","One lower-bound proof, many certification hardness results","Meta-theorem for local certificate lower bounds","Hardness reductions for local certification problems","From 3-coloring to many: local reduction transfer"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Local reductions transfer lower bounds across properties","One lower-bound proof, many certification hardness results","Meta-theorem for local certificate lower bounds","Hardness reductions for local certification problems","From 3-coloring to many: local reduction transfer"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000516,"raw_usage":{"total_tokens":2550,"prompt_tokens":1040,"completion_tokens":1510,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":656,"completion_tokens_details":{"reasoning_tokens":1442}},"tokens_in":656,"tokens_out":1510,"duration_ms":9846,"temperature":1.0,"reasoning_tokens":1442,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T15:00:53.251918+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Locally checkable proofs in distributed computing.Theory Comput., 12(1):1–33, 2016","cited_arxiv_id":null,"evidence_quote":"Supplies the base lower bound for non-3-colorability and the graph construction with the four structural properties used in every pigeonhole argument."},{"cited_title":"Garey, David S","cited_arxiv_id":null,"evidence_quote":"Provides the classical bounded-degree and uncrossing gadgets that preserve 3-colorability in the degree-4 and planar variants."},{"cited_title":"Introduction to the theory of computation","cited_arxiv_id":null,"evidence_quote":"Supplies the 3-SAT-to-Hamiltonian-cycle reduction used to prove the non-Hamiltonicity lower bound."},{"cited_title":"The NP-completeness of edge-coloring.SIAM J","cited_arxiv_id":null,"evidence_quote":"Supplies the 3-SAT-to-edge-coloring reduction used to prove the chromatic-index lower bound."},{"cited_title":"Uniquely colourable graphs and the hardness of colouring graphs of large girth.Comb","cited_arxiv_id":null,"evidence_quote":"Supplies the degree-reducing operation used to push the k-coloring lower bound to maximum degree $k+\\lceil\\sqrt{k}\\rceil-1$."},{"cited_title":"Colouring graphs when the number of colours is almost the maximum degree","cited_arxiv_id":null,"evidence_quote":"Provides the structural theorem on k-colorability of near-maximum-degree graphs that gives the matching logarithmic upper bound at degree $k+\\lceil\\sqrt{k}\\rceil-3$."},{"cited_title":"Renaming in distributed certification","cited_arxiv_id":null,"evidence_quote":"Supplies the identifier-renaming technique that lets the transfer theorem assume identifiers in $\\{1,\\ldots,n\\}$ at $O(\\log n)$ extra cost."}],"review_version":1}