Metraipolis › archive › dc_d2e55ebde1bc
Algorithmic List Decoding at Capacity and Optimal Proximity Gaps for Reed-Solomon Codes — arXiv:2609.05870
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.05870
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T15:01:47.781Z
- SHA-256 of the archived text
2c5c2bfe0b31f7cfc8823669bc2e87eef55e87018c5b65f34abe41716c378638- Stable URL of this page
https://metraipolis.com/documento/dc_d2e55ebde1bc
How to cite
Algorithmic List Decoding at Capacity and Optimal Proximity Gaps for Reed-Solomon Codes — arXiv:2609.05870 — arXiv (en), https://arxiv.org/abs/2609.05870 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_d2e55ebde1bc (Metraipolis archive dc_d2e55ebde1bc, sha256 2c5c2bfe0b31f7cfc8823669bc2e87eef55e87018c5b65f34abe41716c378638)
BibTeX
@misc{dcd2e55ebde1bc,
title = {Algorithmic List Decoding at Capacity and Optimal Proximity Gaps for Reed-Solomon Codes — arXiv:2609.05870},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.05870},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_d2e55ebde1bc; sha256 2c5c2bfe0b31f7cfc8823669bc2e87eef55e87018c5b65f34abe41716c378638},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.05870. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We give a unified hidden-derivative framework for list decoding and mutual correlated agreement of ordinary Reed--Solomon codes over prime fields, on arbitrary prescribed evaluation sets. For every fixed slack $\gamma>0$, every sufficiently large block length $n$, every prime $q\ge n$, and every dimension $1\le k\le(1-\gamma)n$, a deterministic algorithm finds all codewords within relative distance $1-k/n-\gamma$ in $q^{O_\gamma(1)}$ time. The final list has size $n^{O_\gamma(1)}$, independently of $q$. Both statements extend to bounded-input-list recovery, with constants depending additionally on the input-list bound. For every fixed curve degree $\ell$, at most $n^{O_{\gamma,\ell}(1)}$ parameters on a curve $f_0+zf_1+\cdots+z^\ell f_\ell$ admit a nearby codeword whose exact agreement support is not a maximal jointly explained support of the coefficient words. For lines this gives MCA error $n^{O_\gamma(1)}/q$, with no proximity loss. The interpolation stage reparameterizes and optimizes the hidden-derivative construction of Brakensiek, Chen, Putterman, Zhang, and Zheng; differential root enumeration uses Kopparty's algorithm. We then prove that a specialization-safe differential equation has a cover by constant-dimensional varieties of polynomial cumulative degree, outside polynomially many parameter values. Intersecting these varieties with equations from the full agreement support yields both the field-size-independent list bound and exact-support MCA.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-09 in math.IT).
Categorie arXiv: Information Theory (cs.IT).
Pagina del lavoro: https://arxiv.org/abs/2609.05870 — 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-16T14:48:50.694Z dalla pagina https://arxiv.org/catchup/math.IT/2026-09-09?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).