pith. sign in

arxiv: 2511.18420 · v3 · pith:FCFLEK2Bnew · submitted 2025-11-23 · 💻 cs.IT · math.IT

Function-Correcting Codes With Data Protection

Charul Rajput , B. Sundar Rajan , Ragnar Freij-Hollanti , Camilla Hollanti This is my paper

Pith reviewed 2026-05-21 19:02 UTC · model grok-4.3

classification 💻 cs.IT math.IT
keywords function-correcting codesdata protectionerror-correcting codesminimum-distance graphMDS codesperfect codeslinear codesHamming bound
0
0 comments X

The pith

Perfect and MDS codes cannot protect function values beyond the protection given to the data for any function.

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

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.

Core claim

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.

What carries the argument

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.

If this is right

  • 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.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • 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.

Load-bearing premise

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.

What would settle it

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.

Figures

Figures reproduced from arXiv: 2511.18420 by B. Sundar Rajan, Camilla Hollanti, Charul Rajput, Ragnar Freij-Hollanti.

Figure 1
Figure 1. Figure 1: General setup of function-correcting codes. The transmitter has a message vector [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: General network setups 2) In data storage: The general setup of function-correcting codes defined in this paper is also beneficial for storage systems where certain attributes of the data are more important than others. While the entire dataset can be stored with basic error protection, the important attributes or features of the data can be stored with a higher level of protection. This naturally aligns w… view at source ↗
read the original abstract

Function-correcting codes (FCCs) are designed to provide error protection for the value of a function computed on the data. Existing work typically focuses solely on protecting the function value and not the underlying data. In this work, we propose a general framework that offers protection for both the data and the function values. Since protecting the data inherently contributes to protecting the function value, we focus on scenarios where the function value requires stronger protection than the data itself. We first introduce a more general approach and a framework for function-correcting codes that incorporates data protection along with protection of function values. A two-step construction procedure for such codes is proposed, and bounds on the optimal redundancy of general FCCs with data protection are reported. Using these results, we exhibit examples that show that data protection can be added to existing FCCs without increasing redundancy. Using our two-step construction procedure, we present explicit constructions of FCCs with data protection for specific families of functions, such as locally bounded functions and the Hamming weight function. We associate a graph called minimum-distance graph to a code and use it to show that perfect codes and maximum distance separable (MDS) codes cannot provide additional protection to function values over and above the amount of protection for data for any function. Then we focus on linear FCCs and provide some results for linear functions, leveraging their inherent structural properties. To the best of our knowledge, this is the first instance of FCCs with a linear structure. Finally, we generalize the Plotkin and Hamming bounds well known in classical error-correcting coding theory to FCCs with data protection.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 3 minor

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.

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 (1)
  1. [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.
minor comments (3)
  1. [Introduction] 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.
  2. [two-step construction] 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.
  3. [bounds section] 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.

Simulated Author's Rebuttal

1 responses · 0 unresolved

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.

read point-by-point responses

  1. Referee: [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.

    Authors: 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: yes

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper introduces a general framework for FCCs with data protection, proposes a two-step construction, derives bounds as generalizations of classical coding bounds, and exhibits explicit constructions for specific function families. The key claim that perfect and MDS codes cannot provide additional function-value protection is established by associating a minimum-distance graph to any code and showing that its structure forces the effective function distance to equal the code minimum distance for non-constant functions. This argument relies on the graph definition and connectedness properties rather than on any fitted parameters, self-citations, or prior results by the same authors that would reduce the claim to its own inputs. No step equates a prediction to a fitted input by construction, imports uniqueness via self-citation, or renames a known result as a new derivation. The modeling choice to focus on cases where function protection exceeds data protection is stated explicitly as a scope decision, not smuggled in as an assumption that forces the conclusions.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

Relies on standard coding theory background; introduces minimum-distance graph as new concept with no independent evidence outside the paper.

axioms (1)
  • standard math Standard assumptions of error-correcting codes over finite alphabets and linear algebra properties for linear codes
    Implicit throughout discussions of linear FCCs, MDS codes, and bound generalizations.
invented entities (1)
  • Minimum-distance graph no independent evidence
    purpose: To prove that perfect and MDS codes cannot provide extra function protection beyond data protection
    Newly associated to a code for the impossibility result; no falsifiable handle outside the paper

pith-pipeline@v0.9.0 · 5826 in / 1164 out tokens · 69554 ms · 2026-05-21T19:02:40.657769+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

  • IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking unclear
    ?
    unclear

    Relation between the paper passage and the cited Recognition theorem.

    We associate a graph called minimum-distance graph to a code and use it to show that perfect codes and maximum distance separable (MDS) codes cannot provide additional protection to function values over and above the amount of protection for data for any function.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 3 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Function-Correction with Optimal Data Protection for the General Hamming Code Membership

    cs.IT 2026-05 unverdicted novelty 6.0

    A construction for optimal SEFCCs on the Hamming code membership function is given by reducing distance-2 pair minimization to a max-cut problem solved via eigenvectors of distance-4 graphs, with optimality for even n...

  2. Generalized Function-Correcting Partition Codes

    cs.IT 2026-05 conditional novelty 6.0

    Generalized function-correcting partition codes unify protection for multiple message partitions with varying distance requirements and can achieve strictly lower redundancy than summing individual protections or usin...

  3. Existence and Constructions of Strict Function-Correcting Codes with Data Protection

    cs.IT 2026-04 unverdicted novelty 6.0

    Linear codes qualify as strict function-correcting codes with data protection precisely when the subcode generated by their minimum-weight codewords is proper, with chain codes and narrow-sense BCH codes of designed d...

Reference graph

Works this paper leans on

19 extracted references · 19 canonical work pages · cited by 3 Pith papers

  1. [1]

    Function-correcting codes,

    A. Lenz, R. Bitar, A. Wachter-Zeh, and E. Yaakobi, “Function-correcting codes,”IEEE Transactions on Information Theory, vol. 69, no. 9, pp. 5604–5618, Sept. 2023

    work page 2023

  2. [2]

    Is unequal error protection useful?,

    O. Y . Bursalioglu and G. Caire, “Is unequal error protection useful?,” in Proc.2011 IEEE International Symposium on Information Theory (ISIT), Saint Petersburg, Russia, Jul. 2011, pp. 1402–1406

    work page 2011

  3. [3]

    On linear unequal error protection codes,

    B. Masnick and J. Wolf, “On linear unequal error protection codes,”IEEE Transactions on Information Theory, vol. 13, no. 4, pp. 600–607, Oct. 1967

    work page 1967

  4. [4]

    Linear unequal error protection codes,

    I. Boyarinov and G. Katsman, “Linear unequal error protection codes,”IEEE Transactions on Information Theory, vol. 27, no. 2, pp. 168– 175, Mar. 1981

    work page 1981

  5. [5]

    To get a bit of information may be as hard as to get full information,

    R. Ahlswede and I. Csisz ´ar, “To get a bit of information may be as hard as to get full information,”IEEE Transactions on Information Theory, vol. 27, no. 4, pp. 398–408, Jul. 1981

    work page 1981

  6. [6]

    Coding for computing,

    A. Orlitsky and J. R. Roche, “Coding for computing,”IEEE Transactions on Information Theory, vol. 47, no. 3, pp. 903–917, Mar. 2001

    work page 2001

  7. [7]

    Unequal error protection: An information-theoretic perspective,

    S. Borade, B. Nakibo ˘glu, and L. Zheng, “Unequal error protection: An information-theoretic perspective,”IEEE Transactions on Information Theory, vol. 55, no. 12, pp. 5511–5539, Dec. 2009

    work page 2009

  8. [8]

    On distributed computing for functions with certain structures,

    S. Kuzuoka and S. Watanabe, “On distributed computing for functions with certain structures,”IEEE Transactions on Information Theory, vol. 63, no. 11, pp. 7003–7017, Nov. 2017

    work page 2017

  9. [9]

    Context-aware resiliency: Unequal message protection for random- access memories,

    C. Schoeny, F. Sala, M. Gottscho, I. Alam, P. Gupta, and L. Dolecek, “Context-aware resiliency: Unequal message protection for random- access memories,”IEEE Transactions on Information Theory, vol. 65, no. 10, pp. 6146–6159, Oct. 2019

    work page 2019

  10. [10]

    Function-correcting codes for symbol-pair read channels,

    Q. Xia, H. Liu, and B. Chen, “Function-correcting codes for symbol-pair read channels,”IEEE Transactions on Information Theory, vol. 70, no. 11, pp. 7807–7819, Nov. 2024

    work page 2024

  11. [11]

    Optimal redundancy of function-correcting codes,

    G. Ge, Z. Xu, X. Zhang, and Y . Zhang, “Optimal redundancy of function-correcting codes,”arXiv preprint arXiv:2502.16983v1, 2025

    work page arXiv 2025

  12. [12]

    On function-correcting codes,

    R. Premlal and B. S. Rajan, “On function-correcting codes,”IEEE Transactions on Information Theory, vol. 71, no. 8, pp. 5884–5897, Aug. 2025

    work page 2025

  13. [13]

    Function-correcting codes for locally bounded functions,

    C. Rajput, B. S. Rajan, R. Freij-Hollanti, and C. Hollanti, “Function-correcting codes for locally bounded functions,” in Proc.2025 IEEE Information Theory Workshop (ITW), Sydney, Australia, Sept. 2025. Available: arXiv:2504.07804v3

    work page arXiv 2025

  14. [14]

    Function-correctingb-symbol codes for locally (λ, ρ,b)-functions,

    G. K. Verma, A. Singh, and A. K. Singh, “Function-correctingb-symbol codes for locally (λ, ρ,b)-functions,”arXiv preprint arXiv:2505.09473, 2025

    work page arXiv 2025

  15. [15]

    On the redundancy of function-correcting codes over finite fields,

    H. Ly and E. Soljanin, “On the redundancy of function-correcting codes over finite fields,”arXiv preprint arXiv:2504.14410v4, 2025

    work page arXiv 2025

  16. [16]

    Hill,A first course in coding theory

    R. Hill,A first course in coding theory. Oxford University Press, 1986

    work page 1986

  17. [17]

    Ling and C

    S. Ling and C. Xing,Coding Theory: A First Course. Cambridge University Press, 2004

    work page 2004

  18. [18]

    Algebraic methods for secure coded computing,

    O. Makkonen, “Algebraic methods for secure coded computing,” Ph.D. thesis, Department of Mathematics and Systems Analysis, Aalto University, Espoo, Finland, 2025

    work page 2025

  19. [19]

    Bounds on the minimum distance of linear codes and quantum codes,

    M. Grassl, “Bounds on the minimum distance of linear codes and quantum codes,” available at: https://www.codetables.de, accessed in 2025. January 21, 2026 DRAFT 44 Appendix A. Counting the number of vectors in the union of balls of radius t Theorem 18.Consider two Hamming balls B(u,t)and B(v,t)for u,v∈F n q such that d(u,v)=1. Then |B(u,t)∪B(v,t)|=2 tX i=...

    work page 2025