Algorithmic List Decoding at Capacity and Optimal Proximity Gaps for Reed-Solomon Codes
Abstract
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 γ>0, every sufficiently large block length n, every prime q≥ n, and every dimension 1≤ k≤(1−γ)n, a deterministic algorithm finds all codewords within relative distance 1−k/n−γ in qOγ(1) time. The final list has size nOγ(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 ℓ, at most nOγ,ℓ(1) parameters on a curve f0+zf1+⋯+zℓ fℓ 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 nOγ(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.
Related
- Reed-Solomon Codes at Capacity: Algorithmic List-Decoding and Proximity Gaps
- Algorithmic List Decoding of Reed-Solomon Codes up to Capacity
- Explicit Reed-Solomon Subspace Designs: Optimal List and Line Decoding
- Insdel Reed-Solomon Decoding Algorithms up to the Half-Singleton Bound
- Combinatorial limitations of list-decoding Reed-Solomon codes
BibTeX
@misc{jeronimo2026algorithmic,
title = {{Algorithmic List Decoding at Capacity and Optimal Proximity Gaps for Reed-Solomon Codes}},
author = {Fernando Granha Jeronimo},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.05870},
eprint = {2609.05870},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.05870},
}
RIS
TY - UNPB
TI - Algorithmic List Decoding at Capacity and Optimal Proximity Gaps for Reed-Solomon Codes
AU - Fernando Granha Jeronimo
PY - 2026
DA - 2026/09/05
PB - arXiv
DO - 10.48550/arxiv.2609.05870
UR - https://arxiv.org/abs/2609.05870
AB - 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 γ>0, every sufficiently large block length n, every prime q≥ n, and every dimension 1≤ k≤(1−γ)n, a deterministic algorithm finds all codewords within relative distance 1−k/n−γ in q^O_γ(1) time. The final list has size n^O_γ(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 ℓ, at most n^O_γ,ℓ(1) parameters on a curve f_0+zf_1+⋯+z^ℓ f_ℓ 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_γ(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.
ER -