{"id":"87d90f11-49f0-421a-9521-01f3e6291aa4","arxiv_id":"2511.18420","paper_version":3,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Develops a general framework and explicit constructions for function-correcting codes with data protection, including bounds and results for linear codes and specific functions.","lead":"This paper introduces a framework for function-correcting codes that protect both the underlying data and the values of functions computed on that data, focusing on cases needing stronger function protection. It offers two-step constructions, redundancy bounds, and generalizations of classical coding bounds like Plotkin and Hamming.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.3","headline":"No significant objection identified","rationale":"The reader's weakest assumption concerns the modeling premise that data protection contributes to function protection. That premise is foundational to the whole framework but is not the load-bearing step for the specific perfect/MDS claim, which is proved separately via the graph construction. Because the full text supplies the graph definition and the explicit statement that the result holds for any function, and no technical gap appears in the argument, the UNVERDICTED verdict does not require adjustment.","tokens_in":1781,"tokens_out":395,"duration_ms":124439,"concrete_test":"For the [7,4,3] Hamming code, build the Cayley graph on the 16 codewords with edges given by the 7 minimum-weight (weight-3) codewords; confirm it is connected. Repeat for a small MDS code (e.g., [4,2,3] Reed-Solomon over GF(5)) by enumerating all pairs at distance 3 and checking connectivity of the resulting graph. If both graphs are connected, the claim holds for these canonical examples.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim associates a minimum-distance graph to a code to conclude that perfect codes and MDS codes cannot provide function-value protection beyond the data-protection level for any function. This rests on the graph connecting codewords at exact minimum distance; its connectedness (or single-component structure) forces any non-constant function to have at least one minimum-distance pair with differing values, so the effective distance for the function equals the code minimum distance. The manuscript presents this after the general framework and before the linear-FCC section, indicating the argument is intended to apply to both linear and nonlinear cases. No internal inconsistency, hidden assumption on linearity, or mismatch with the definition of additional protection (d_f > d_min while preserving data-correction radius) is apparent from the construction.","agreement_with_reader":"disagree"},"referee_report":{"model":"grok-4.3","summary":"The paper proposes a general framework for function-correcting codes (FCCs) that simultaneously protect both the underlying data and the values of functions computed on that data. It introduces a two-step construction, derives bounds on optimal redundancy for general FCCs with data protection, provides examples where data protection can be added to existing FCCs without extra redundancy, gives explicit constructions for locally bounded functions and the Hamming weight function, associates a minimum-distance graph to a code to prove that perfect codes and MDS codes cannot provide additional function-value protection beyond the data-protection level for any function, presents initial results for linear FCCs, and generalizes the classical Plotkin and Hamming bounds to this setting.","tokens_in":1919,"tokens_out":584,"duration_ms":47129,"significance":"If the results hold, the work meaningfully extends function-correcting code theory by incorporating data protection, a natural extension given that data protection inherently aids function protection. The minimum-distance graph provides a clean combinatorial tool for impossibility results on perfect and MDS codes, the explicit constructions for specific function families are concrete and useful, and the first linear FCC results open a structured-code direction. The generalized bounds may serve as a foundation for further coding-theoretic developments in applications requiring joint data and function reliability.","major_comments":[{"comment":"The central impossibility result (that perfect codes and MDS codes cannot achieve d_f > d_min for any function) is established via the minimum-distance graph in the section following the general framework. The argument requires that this graph is connected (or has a single component) for these code families, forcing any non-constant function to differ on at least one minimum-distance pair and thereby equating the effective function distance to the code minimum distance. The manuscript should explicitly define the edge set of the minimum-distance graph and prove its connectedness property for perfect and MDS codes, as this step is load-bearing for the claim.","section":"minimum-distance graph section"}],"minor_comments":[{"comment":"The abstract states that 'protecting the data inherently contributes to protecting the function value' and focuses on cases where the function requires stronger protection. This modeling choice should be illustrated with a short concrete example early in the introduction to clarify the regime of interest.","section":"Introduction"},{"comment":"In the two-step construction procedure, the notation for the intermediate code and the final FCC with data protection should be made consistent across the text and any accompanying figures or tables.","section":"two-step construction"},{"comment":"The generalized Plotkin and Hamming bounds are stated for FCCs with data protection; a brief comparison table or remark contrasting them with the classical versions would improve readability.","section":"bounds section"}],"recommendation":"minor_revision","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for the positive evaluation of our work and for the constructive major comment. We address the point below and will incorporate the requested clarifications to strengthen the presentation of the minimum-distance graph and the associated impossibility results.","responses":[{"response":"We agree with the referee that an explicit definition of the edge set and a proof of connectedness are necessary for rigor. In the revised manuscript we will define the minimum-distance graph G_C of a code C as the graph whose vertices are the codewords of C, with an undirected edge between distinct codewords x and y if and only if d(x,y) equals the minimum distance d_min of C. We will then prove that G_C is connected for any perfect code: because the spheres of radius t around the codewords partition the ambient space, any two codewords can be joined by a path of successive minimum-distance steps that stay inside the code. For MDS codes we will prove connectedness by exploiting the fact that any two distinct codewords differ in at least d_min positions and that the MDS property allows the construction of intermediate codewords that realize a chain of distance-d_min steps; the argument holds for both Reed-Solomon codes and their generalizations. These additions will be placed immediately after the definition of the graph in the section following the general framework.","revision_made":"yes","referee_comment":"[minimum-distance graph section] The central impossibility result (that perfect codes and MDS codes cannot achieve d_f > d_min for any function) is established via the minimum-distance graph in the section following the general framework. The argument requires that this graph is connected (or has a single component) for these code families, forcing any non-constant function to differ on at least one minimum-distance pair and thereby equating the effective function distance to the code minimum distance. The manuscript should explicitly define the edge set of the minimum-distance graph and prove its connectedness property for perfect and MDS codes, as this step is load-bearing for the claim."}],"tokens_in":1478,"tokens_out":425,"duration_ms":25412,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"Hi, the main point is that this work builds a framework for function-correcting codes that protect the data as well as the function value. They focus on cases where the function needs stronger protection than the data alone, introduce a two-step construction, give explicit builds for locally bounded functions and Hamming weight, and prove via a minimum-distance graph that perfect and MDS codes cannot add any further function protection beyond the data level. They also generalize the Plotkin and Hamming bounds to this setting and show some cases where data protection can be added to prior FCCs without extra redundancy. The linear FCC results are new and use the structure of linear functions directly. These pieces are distinct from the earlier FCC literature cited in the abstract. The constructions and bound generalizations are the parts that hold up cleanly and give concrete value. The graph argument for the impossibility result on perfect and MDS codes looks consistent with the definitions given; it connects codewords at exact minimum distance and uses connectedness to force differing function values on at least one such pair for non-constant functions. No internal mismatch appears between the linear and nonlinear cases or with the extra-protection condition. The modeling choice to treat data protection as already helping the function is reasonable and lets them target the stronger-function case without circularity. This is aimed at coding theorists working on reliable function computation or distributed systems. A reader who follows bounds, constructions, and extensions of classical coding results will get usable material from the examples and generalizations. It is not a broad leap but a clear incremental step with enough new pieces to merit referee time. I would send it for peer review.","headline":"This paper adds a framework for function-correcting codes that protect both data and function values, with a two-step construction, the first linear FCC results, explicit examples, and a graph argument showing perfect and MDS codes give no extra function protection.","tokens_in":2396,"tokens_out":411,"would_cite":false,"duration_ms":31890,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"Perfect and MDS codes cannot protect function values beyond the protection given to the data for any function.","keywords":["function-correcting codes","data protection","error-correcting codes","minimum-distance graph","MDS codes","perfect codes","linear codes","Hamming bound"],"falsifier":"An explicit perfect code (or MDS code) together with a function for which the minimum distance needed to protect the function value exceeds the minimum distance needed to protect the data.","tokens_in":2703,"feed_emoji":"🛡️","tokens_out":702,"duration_ms":42363,"temperature":0.7,"pith_summary":"The paper develops a framework for function-correcting codes that simultaneously protect the underlying data and the value of a function computed on it. Because data protection already contributes to function protection, the work concentrates on cases where the function requires strictly stronger protection and supplies a two-step construction method along with bounds on the extra redundancy needed. Explicit constructions are given for locally bounded functions and the Hamming weight function, and a minimum-distance graph is introduced to prove that perfect codes and maximum-distance-separable codes add no extra function protection. The authors also treat linear function-correcting codes for the first time and extend the classical Plotkin and Hamming bounds to this setting.","feed_headline":"Perfect codes give no extra protection to function values beyond data","feed_subtitle":"A minimum-distance graph proves this for any function, while two-step constructions add data protection at no extra cost.","key_machinery":"The minimum-distance graph associated to a code, which encodes the distances between codewords and is used to compare the protection level of the data against the protection level of any function value.","core_discovery":"By associating a minimum-distance graph to any code, the authors show that perfect codes and MDS codes cannot provide additional protection to function values over and above the amount of protection already supplied for the data itself, for any function. A two-step construction procedure is given that allows data protection to be added to existing function-correcting codes without increasing redundancy, and explicit constructions are obtained for locally bounded functions and the Hamming-weight function. Linear function-correcting codes are introduced, and the Plotkin and Hamming bounds are generalized to the data-protection setting.","pith_inferences":["The minimum-distance-graph argument may extend to other families of codes beyond perfect and MDS codes.","The two-step construction suggests a modular design approach in which data protection is handled first and function-specific protection is added only when required.","Linear function-correcting codes open the possibility of efficient encoding and decoding algorithms that exploit linearity for both data and function protection."],"forward_implications":["Data protection can be added to some existing function-correcting codes at no extra redundancy cost.","Explicit constructions exist for locally bounded functions and the Hamming-weight function that protect both data and function values.","Linear function-correcting codes with data protection are possible and inherit structural properties of linear codes.","The classical Plotkin and Hamming bounds extend directly to the setting of function-correcting codes with data protection."],"fun_headline_variants":["Perfect codes give zero extra function protection beyond data","Minimum-distance graph proves perfect codes protect no extra function value","Two-step construction adds data protection to FCCs with no redundancy added","Plotkin and Hamming bounds generalized for FCCs with data protection"],"cache_read_input_tokens":64,"weakest_assumption_plain":"That protecting the data inherently contributes to protecting the function value, so that the interesting case is when the function needs strictly more protection than the data.","fun_headline_variants_meta":{"raw":{"variants":["Perfect codes give zero extra function protection beyond data","Minimum-distance graph proves perfect codes protect no extra function value","Two-step construction adds data protection to FCCs with no redundancy added","Plotkin and Hamming bounds generalized for FCCs with data protection"]},"model":"grok-4.3","cost_usd":0.01399,"raw_usage":{"total_tokens":6007,"prompt_tokens":768,"num_sources_used":0,"completion_tokens":67,"cost_in_usd_ticks":139903000,"prompt_tokens_details":{"text_tokens":768,"audio_tokens":0,"image_tokens":0,"cached_tokens":64},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":5172,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":768,"tokens_out":67,"duration_ms":85460,"temperature":1.0,"reasoning_tokens":5172,"cache_read_input_tokens":64,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-05-21T19:02:40.657769+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"An explicit perfect code (or MDS code) together with a function for which the minimum distance needed to protect the function value exceeds the minimum distance needed to protect the data.","supporting_citations":[],"review_version":1}