On the Redundancy of Function-Correcting Codes over Finite Fields
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913938693685248 |
|---|---|
| author | Ly, Hoang Soljanin, Emina |
| author_facet | Ly, Hoang Soljanin, Emina |
| contents | Function-correcting codes (FCCs) protect specific function evaluations of a message against errors. This condition imposes a less stringent distance requirement than classical error-correcting codes (ECCs), allowing for reduced redundancy. FCCs were introduced by Lenz et al. (2021), who also established a lower bound on the optimal redundancy for FCCs over the binary field. Here, we derive an upper bound within a logarithmic factor of this lower bound. We show that the same lower bound holds for any finite field. Moreover, we show that this bound is tight for sufficiently large fields by demonstrating that it also serves as an upper bound. Furthermore, we construct an encoding scheme that achieves this optimal redundancy. Finally, motivated by these two extreme regimes, we conjecture that our bound serves as a valid upper bound across all finite fields. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_14410 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the Redundancy of Function-Correcting Codes over Finite Fields Ly, Hoang Soljanin, Emina Information Theory Function-correcting codes (FCCs) protect specific function evaluations of a message against errors. This condition imposes a less stringent distance requirement than classical error-correcting codes (ECCs), allowing for reduced redundancy. FCCs were introduced by Lenz et al. (2021), who also established a lower bound on the optimal redundancy for FCCs over the binary field. Here, we derive an upper bound within a logarithmic factor of this lower bound. We show that the same lower bound holds for any finite field. Moreover, we show that this bound is tight for sufficiently large fields by demonstrating that it also serves as an upper bound. Furthermore, we construct an encoding scheme that achieves this optimal redundancy. Finally, motivated by these two extreme regimes, we conjecture that our bound serves as a valid upper bound across all finite fields. |
| title | On the Redundancy of Function-Correcting Codes over Finite Fields |
| topic | Information Theory |
| url | https://arxiv.org/abs/2504.14410 |