{"id":"f3dd40d5-49f9-43f7-9c5f-a6ceada27e80","arxiv_id":"2606.04934","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Parity of network size can be locally certified with constant bits using IDs at radius 2 or in bounded-expansion graphs at radius 1, but needs Ω(log log* n) bits in anonymous radius-1 model.","lead":"This paper shows that certifying the parity of network size can be done with constant-size certificates in graphs with identifiers at verification radius 2 and in bounded-expansion classes at radius 1, but requires Ω(log log* n) bits in anonymous graphs at radius 1. A smart generalist might read it to see how model choices and graph structure affect the feasibility of local verification for a basic global property.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.3","headline":"Higher-order Ramsey argument for Ω(log log* n) lower bound in anonymous radius-1 model may not fully capture certificate interactions","rationale":"The reader's weakest_assumption directly identifies the novel combinatorial argument as the load-bearing step; the upper-bound claims (constant-bit parent encoding via IDs and conflict-free colorings, constant certificates in bounded-expansion classes) rest on more standard local techniques and appear less fragile. Because the full text was referenced but the abstract alone supplies the landscape, the same concern remains the single most load-bearing one.","tokens_in":1855,"tokens_out":316,"duration_ms":22085,"concrete_test":"From the lower-bound section, extract the precise topology family T and the Ramsey statement R used; construct an explicit certificate assignment of size o(log log* n) on T that satisfies the radius-1 verification condition for even parity and check whether it violates R.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central lower-bound claim requires that the new technique (complex topologies + higher-order Ramsey arguments) forces any radius-1 certificate assignment in anonymous networks to use Ω(log log* n) bits for parity. This holds only if the reduction correctly maps every possible local certificate function to a combinatorial object whose size is bounded below by the Ramsey number, without extra assumptions on how certificates can encode global parity information via their distribution alone. The abstract and described tools do not make this mapping explicit enough to rule out a gap where the argument applies only to a restricted class of certificate structures.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","summary":"The paper studies local certification of the parity property (network size congruent to a fixed value) across models. It claims that in general graphs with unique identifiers and verification radius 2, constant-size certificates suffice; in anonymous graphs with radius 1, Ω(log log* n) bits are required via a new technique using complex topologies and higher-order Ramsey arguments; and in bounded-expansion classes (e.g., bounded-degree or planar graphs), constant-size certificates exist even in the anonymous radius-1 model. New tools are introduced for encoding a parent pointer at each node using constant bits (via implicit IDs and conflict-free colorings).","tokens_in":1966,"tokens_out":398,"duration_ms":25829,"significance":"If the central claims hold, the work establishes a nuanced separation for a basic global property, showing how identifiers, verification radius, and graph class restrictions interact with certification size. The new lower-bound technique based on higher-order Ramsey arguments and the parent-encoding method are explicit strengths that could transfer to other local certification problems; the paper grounds results in independent combinatorial arguments rather than fitted parameters.","major_comments":[{"comment":"The section presenting the Ω(log log* n) lower bound: the reduction must explicitly map every possible radius-1 certificate assignment (including those that might encode global parity via distribution patterns alone) onto a combinatorial object whose size is forced below by the higher-order Ramsey number; without this explicit mapping shown for arbitrary certificate functions, the bound does not necessarily apply to all certificate structures.","section":"lower-bound technique (complex topologies and higher-order Ramsey arguments)"}],"minor_comments":[{"comment":"Abstract: states the three main results and new tools but supplies no proof sketches, certificate constructions, or verification steps for the Ramsey arguments, which hinders immediate assessment of soundness.","section":"Abstract"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for the positive evaluation of the paper's significance and for highlighting the contributions of the new lower-bound technique and parent-encoding method. We address the single major comment below.","responses":[{"response":"The lower-bound argument is constructed precisely to apply to an arbitrary certificate assignment function. We begin by fixing any function that, in the anonymous radius-1 model, assigns certificates of size o(log log* n) to each node on the basis of its closed neighborhood. This function induces, on any graph we later construct, a labeling of the vertices by the (finitely many) possible certificate strings. The complex topologies are then built so that their vertex sets can be partitioned into a constant number of classes whose induced subgraphs admit higher-order Ramsey numbers large enough to guarantee a large monochromatic clique (or analogous uniform substructure) under any such labeling. Inside that monochromatic substructure we embed a parity gadget whose local views are identical under the certificate function, yet whose global parity differs from the one the certificates are required to certify. Because the Ramsey extraction depends only on the existence of the labeling and not on any particular way the labels were chosen (including distribution patterns across the graph), the contradiction holds for every possible certificate function of sub-log-log* size. The mapping from certificate function to combinatorial object is therefore the induced labeling itself, which is defined for arbitrary functions.","revision_made":"no","referee_comment":"[lower-bound technique (complex topologies and higher-order Ramsey arguments)] The section presenting the Ω(log log* n) lower bound: the reduction must explicitly map every possible radius-1 certificate assignment (including those that might encode global parity via distribution patterns alone) onto a combinatorial object whose size is forced below by the higher-order Ramsey number; without this explicit mapping shown for arbitrary certificate functions, the bound does not necessarily apply to all certificate structures."}],"tokens_in":1429,"tokens_out":401,"duration_ms":19674,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The core contribution is a set of matching upper and lower bounds that separate the models. With identifiers and radius 2, they get constant-size certificates; without identifiers and with radius 1 they prove an Omega(log log* n) lower bound via new Ramsey-style arguments on complex topologies; and the lower bound vanishes on bounded-expansion graphs, where constant certificates exist again. They also supply a constant-bit way to encode a parent pointer using IDs and conflict-free colorings.\n\nThese distinctions are new. Earlier lower-bound methods did not work on parity, so the Ramsey technique is the main technical step forward. The upper bounds close open cases.\n\nThe obvious soft spot is that the lower-bound argument is only sketched in the abstract. It needs the reduction from arbitrary radius-1 certificate functions to the combinatorial objects to be tight; any looseness there would drop the bound. The rest of the claims look standard once the new tool is granted.\n\nThis is for people working on local certification and distributed verification. The results are concrete enough and the open question they settle is real enough that a serious referee should see it.","headline":"The paper maps a clean landscape for parity certification: constant bits with radius 2 in ID graphs, Omega(log log* n) in anonymous radius-1 graphs, and constant again in bounded-expansion classes.","tokens_in":2438,"tokens_out":312,"would_cite":true,"duration_ms":12539,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"Parity of network size can be certified with constant bits using identifiers at radius 2 or in bounded-expansion classes, but requires Ω(log log* n) bits in anonymous radius-1 general graphs.","keywords":["local certification","parity certification","distributed verification","anonymous networks","bounded expansion","certificate complexity","verification radius","Ramsey arguments"],"falsifier":"An explicit constant-size certificate scheme that correctly certifies parity on every anonymous graph at verification radius 1, or a concrete family of graphs where the Ramsey-type construction fails to produce the claimed size lower bound.","tokens_in":2762,"feed_emoji":"🔢","tokens_out":748,"duration_ms":21988,"temperature":0.7,"pith_summary":"The paper establishes a trichotomy for the local certification of parity across models and graph families. With unique node identifiers and verification radius 2, a constant number of bits per node suffices to certify that the total number of nodes is even. In anonymous networks restricted to radius-1 verification, however, the certificate size must grow at least as Ω(log log* n) on general graphs. The same lower bound disappears in bounded-expansion classes, where constant-size certificates again work under the stricter anonymous radius-1 rules.","feed_headline":"Parity certification needs Ω(log log* n) bits in anonymous radius-1 graphs","feed_subtitle":"Constant bits suffice with identifiers at radius 2 or inside bounded-expansion classes such as planar graphs","key_machinery":"A lower-bound technique that constructs complex graph topologies and invokes higher-order Ramsey-type arguments to force large certificates, combined with an encoding that implicitly assigns each node a parent pointer using a constant number of bits via identifiers and conflict-free colorings.","core_discovery":"Parity certification exhibits three distinct regimes: constant-size certificates suffice when identifiers are present and verification reaches distance 2; Ω(log log* n) bits are necessary in fully anonymous graphs at radius 1; and constant-size certificates are again possible in any bounded-expansion class even without identifiers and at radius 1. These results are obtained by a new method for encoding a parent pointer at each node with constantly many bits and by a lower-bound argument that deploys complex topologies together with higher-order Ramsey-type combinatorial arguments.","pith_inferences":["The jump from radius 1 to radius 2 can collapse certificate size for global counting properties even when identifiers are absent.","Many other modular or counting properties that are hard in general graphs may admit constant-size certificates inside bounded-expansion classes.","The new Ramsey-style lower-bound method could separate certificate sizes for additional arithmetic predicates beyond parity.","Whether a graph class admits small parity certificates may serve as a practical test for the bounded-expansion property."],"forward_implications":["Identifiers plus one extra verification hop reduce parity certification to constant bits on arbitrary graphs.","Anonymous radius-1 certification of parity on general graphs requires certificates whose bit length grows with Ω(log log* n).","Every bounded-expansion class admits constant-size anonymous radius-1 certificates for parity.","The parent-pointer encoding technique can be reused to certify tree structures or other local consistency properties with small certificates.","Higher-order Ramsey arguments provide a new combinatorial tool for proving certificate-size lower bounds in local verification."],"fun_headline_variants":["Parity certification has three distinct complexity regimes","IDs allow constant parity certs at verification radius 2","Anonymous radius 1 parity certs need Omega(log log* n) bits","Bounded expansion graphs enable constant parity certification"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"The combinatorial argument that deploys complex topologies and higher-order Ramsey-type reasoning correctly forces any anonymous radius-1 certification of parity to use certificates of size Ω(log log* n).","fun_headline_variants_meta":{"raw":{"variants":["Parity certification has three distinct complexity regimes","IDs allow constant parity certs at verification radius 2","Anonymous radius 1 parity certs need Omega(log log* n) bits","Bounded expansion graphs enable constant parity certification"]},"model":"grok-4.3","cost_usd":0.005508,"raw_usage":{"total_tokens":2614,"prompt_tokens":768,"num_sources_used":0,"completion_tokens":63,"cost_in_usd_ticks":55078000,"prompt_tokens_details":{"text_tokens":768,"audio_tokens":0,"image_tokens":0,"cached_tokens":64},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":1783,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":768,"tokens_out":63,"duration_ms":18233,"temperature":1.0,"reasoning_tokens":1783,"cache_read_input_tokens":64,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-06-28T04:20:44.051657+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"An explicit constant-size certificate scheme that correctly certifies parity on every anonymous graph at verification radius 1, or a concrete family of graphs where the Ramsey-type construction fails to produce the claimed size lower bound.","supporting_citations":[],"review_version":1}