Metraipolis › archive › dc_d925b583a01a
On Optimal Encodings and Systematicity in Function-Correcting Codes — arXiv:2610.09011
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.09011
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-08T12:46:24.223Z
- SHA-256 of the archived text
dd1659ac1e15caa5c4a02df574c9bacd4c6af0b7fc3c06b59a2a1a9b1a341ec1- Stable URL of this page
https://metraipolis.com/documento/dc_d925b583a01a
How to cite
On Optimal Encodings and Systematicity in Function-Correcting Codes — arXiv:2610.09011 — arXiv (en), https://arxiv.org/abs/2610.09011 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_d925b583a01a (Metraipolis archive dc_d925b583a01a, sha256 dd1659ac1e15caa5c4a02df574c9bacd4c6af0b7fc3c06b59a2a1a9b1a341ec1)
BibTeX
@misc{dcd925b583a01a,
title = {On Optimal Encodings and Systematicity in Function-Correcting Codes — arXiv:2610.09011},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.09011},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_d925b583a01a; sha256 dd1659ac1e15caa5c4a02df574c9bacd4c6af0b7fc3c06b59a2a1a9b1a341ec1},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.09011. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Function-correcting codes (FCCs) protect the value of a function $f$ of the message against $t$ errors. In the original formulation of Lenz et al. (2023), the encoding is systematic, and the lower bound of $2t$ on the redundancy relies on this form. Recently, D. Ho (arXiv, 2026) showed, for linear functions and linear encodings, that systematicity can cost redundancy. We begin with the OR function to show that the cost is not confined to the linear setting: a non-systematic encoding attains redundancy $1$ while every systematic encoding needs $2t$. For a linear function $f$ and a fixed linear code $C$, let $d_f$ denote the minimum distance between codewords of messages with different function values. Different generator matrices of $C$ assign different codewords to the messages and can give different values of $d_f$. We study which generator matrix of $C$ gives the largest $d_f$. We give an algorithm that constructs an optimal generator matrix and determines the optimal value as the weight of a codeword in a greedy basis of $C$. We then characterize, in terms of information sets, when a generator matrix in systematic form attains this optimum, and give a necessary condition that is checked on the low-weight codewords of $C$ alone. For two-valued functions, we drop both linearity and systematicity. Using the minimality of initial segments of the simplicial order with respect to Hamming neighbourhoods, we show that a non-systematic $(f,t)$-FCC of length $n$ exists if and only if a condition depending on $f$ only through the size of its smaller preimage holds. For $t=1$, redundancy $1$ is sufficient for every nonconstant two-valued function on $\mathbb{F}_2^k$ with $k\ge 10$. For general $t$, redundancy $1$ suffices for all two-valued functions once $k$ is large enough, and for each $s<2t$ we give an upper bound on the threshold in $k$ beyond which redundancy $s$ suffices.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.IT, nuovi lavori del giorno).
Categorie arXiv: Information Theory (cs.IT).
Pagina del lavoro: https://arxiv.org/abs/2610.09011 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T12:17:15.205Z dalla pagina https://arxiv.org/list/math.IT/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).