Reed–Solomon (RS) codes with randomly chosen evaluation points over linear-size fields are known (2023–2025) to achieve list-decoding capacity: for any rate RR and gap ε\varepsilon, a random puncturing over a field of size O(n)O(n) is (1−R−ε,O(1/ε))(1-R-\varepsilon, O(1/\varepsilon))-list-decodable with high probability, and over exponentially large fields RS codes even attain the exact Shangguan–Tamo generalized Singleton bound. All of these existence results are non-constructive. The surviving open problem, stated as a further direction by Ferber, Kwan, and Sauermann (FOCS 2021 / IEEE Trans. Inf. Theory 2022) after their Ω(ε)\Omega(\varepsilon)-rate, (1−ε,O(1/ε))(1-\varepsilon, O(1/\varepsilon))-list-decodable RS codes over almost-linear fields, is constructive: give a deterministic, efficiently computable, explicit choice of evaluation points α1,…,αn∈Fq\alpha_1,\dots,\alpha_n\in\mathbb{F}_q with q≤poly(n)q\le\mathrm{poly}(n) such that the resulting plain RS code achieves the same list-decodability. Explicit capacity-achieving folded RS codes, multiplicity codes, expander codes, and RS subcodes are now known, but no plain RS construction attaining the optimal list size O(1/ε)O(1/\varepsilon) is known.

Background

A Reed–Solomon (RS) code is obtained by fixing a finite field Fq\mathbb{F}_q of size qq, distinct evaluation points α1,…,αn∈Fq\alpha_1,\dots,\alpha_n\in\mathbb{F}_q, and a dimension kk, and encoding a polynomial ff of degree less than kk by its evaluations (f(α1),…,f(αn))(f(\alpha_1),\dots,f(\alpha_n)). Its rate is R=k/nR=k/n, and it is an MDS code (maximum distance separable: minimum distance exactly n−k+1n-k+1).

A code is (ρ,L)(\rho,L)-list-decodable if every Hamming ball of relative radius ρ\rho (i.e. balls around received words agreeing with the center in at least a 1−ρ1-\rho fraction of coordinates) contains at most LL codewords; the decoder may then return a short list of candidate messages. A stronger guarantee is average-radius list-decodability, where the average distance of any L+1L+1 distinct codewords from any center is at least ρ\rho.

Two classical benchmarks frame the problem. The list-decoding capacity theorem says no code family with rate above 1−H(ρ)1-H(\rho) (where HH is the qq-ary entropy function) can be (ρ,L)(\rho,L)-list-decodable with LL subexponential in nn; conversely random codes of any lower rate achieve this. For radius ρ=1−ε\rho=1-\varepsilon with small ε\varepsilon, capacity means rate arbitrarily close to ε\varepsilon with list size O(1/ε)O(1/\varepsilon). The Johnson bound, a general consequence of distance alone, implies that every RS code of rate ε2\varepsilon^2 is already (1−ε,poly(n))(1-\varepsilon,\mathrm{poly}(n))-list-decodable; 'beating the Johnson bound' means list-decodability at radius 1−ε1-\varepsilon with rate substantially larger than Θ(ε2)\Theta(\varepsilon^2), ideally the capacity-optimal Θ(ε)\Theta(\varepsilon), something the distance-based argument cannot deliver.

Guo, Li, Shangguan, Tamo, and Wootters (SIAM J. Comput. 2024; arXiv:2011.04453) first proved existence of RS codes beating the Johnson radius, but needed exponentially large fields. Ferber, Kwan, and Sauermann (arXiv:2012.10584) improved this to almost-linear field size: for every ε\varepsilon there exist (1−ε,O(1/ε))(1-\varepsilon,O(1/\varepsilon))-list-decodable RS codes of rate Ω(ε)\Omega(\varepsilon) once q≥n1+δq\ge n^{1+\delta}. Their proof analyzes random puncturings (random choices of the evaluation points) of high-distance codes, and is non-constructive. Shangguan and Tamo (arXiv:1911.01502) formulated the exact optimum: a generalized Singleton bound on list-decodability, conjectured tight for most RS codes over large enough fields.

This conjectured exact trade-off was then resolved over exponentially large fields by Brakensiek, Gopi, and Makam (STOC 2023): generic RS codes attain their generalized Singleton bound with list size LL at radius L/(L+1)⋅(1−R)L/(L+1)\cdot(1-R). Alrabiah, Guo, Guruswami, Li, and Zhang (Advances in Combinatorics 2025) brought the field size down to linear: a random punctured RS code over any field with q≥n+k⋅210L/εq\ge n+k\cdot 2^{10L/\varepsilon} is (LL+1(1−R−ε),L)(\tfrac{L}{L+1}(1-R-\varepsilon),L) average-radius list-decodable with high probability, which at L=O(1/ε)L=O(1/\varepsilon) and fixed ε\varepsilon means field size O(n)O(n) — optimal up to constants, since distinct evaluation points force q≥nq\ge n. Their paper also records that exactly attaining the generalized Singleton bound provably requires exponentially large fields, so the capacity-level (constant-slack) statement is the best one can hope for over small fields — and it is now achieved, but only via the probabilistic method.

On the explicit side, several related families are now settled: Chen and Zhang (STOC 2025) proved that explicit folded RS codes (where the polynomial is evaluated on overlapping tuples of points, so each codeword coordinate is a block of evaluations) and multiplicity codes (which record the polynomial together with its derivatives at each point) achieve capacity with optimal list size O(1/ε)O(1/\varepsilon) over polynomial alphabets; Jeronimo, Mittal, Srivastava, and Tulsiani (STOC 2025) gave non-algebraic expander-based explicit codes approaching the generalized Singleton bound; and Berman, Shany, and Tamo (IEEE Trans. Inf. Theory 2025) constructed explicit subcodes of RS codes (built from tensor products of RS codes with cyclic row shifts) that efficiently achieve capacity with constant list size. None of these is a plain RS code: each changes the code family rather than making the full RS code itself list-decodable. Deterministic list decoding of plain RS codes over prime fields of linear size up to capacity with polynomial-size lists is now known for every evaluation set (arXiv:2609.08005; arXiv:2609.05870), but not with the optimal list size O(1/ε)O(1/\varepsilon).

Problem Statement

Construct an explicit family of Reed–Solomon codes that achieves capacity-level list-decodability over a small field. Formally: give a deterministic algorithm, running in time polynomial in nn and log⁡q\log q, that on input nn, rate R∈(0,1)R\in(0,1) and ε>0\varepsilon>0 outputs distinct evaluation points α1,…,αn∈Fq\alpha_1,\dots,\alpha_n\in\mathbb{F}_q with q≤poly(n)q\le\mathrm{poly}(n) (ideally q=O(n)q=O(n), which random choice achieves and is optimal up to constants), such that the resulting [n,k][n,k] Reed–Solomon code with k=⌈Rn⌉k=\lceil Rn\rceil is (1−R−ε,O(1/ε))(1-R-\varepsilon, O(1/\varepsilon))-list-decodable (average-radius list-decodability would be stronger and is what the known existence results provide). As usual, all asymptotic notation is in nn with RR and ε\varepsilon fixed; the hidden constants in O(1/ε)O(1/\varepsilon), the runtime bound, and the polynomial in q≤poly(n)q\le\mathrm{poly}(n) may depend on RR and ε\varepsilon, matching the convention in the cited existence results. In the large-radius formulation of Ferber–Kwan–Sauermann this is the case R=Θ(ε)R=\Theta(\varepsilon): explicit points over a polynomial-size field giving rate Ω(ε)\Omega(\varepsilon) codes that are (1−ε,O(1/ε))(1-\varepsilon,O(1/\varepsilon))-list-decodable. The problem is the derandomization of the known probabilistic-method results: random evaluation points work with high probability, and the question is whether an explicit, efficiently computable choice can match them.

References

  1. Asaf Ferber, Matthew Kwan, Lisa Sauermann, List-Decodability With Large Radius for Reed-Solomon Codes, IEEE Transactions on Information Theory (2022), DOI 10.1109/TIT.2022.3148779, preprint arXiv:2012.10584, https://doi.org/10.1109/TIT.2022.3148779
  2. Chong Shangguan, Itzhak Tamo, Combinatorial List-Decoding of Reed-Solomon Codes Beyond the Johnson Radius, STOC 2020, DOI 10.1145/3357713.3384295, preprint arXiv:1911.01502, https://doi.org/10.1145/3357713.3384295
  3. Zeyu Guo, Ray Li, Chong Shangguan, Itzhak Tamo, Mary Wootters, Improved List-Decodability and List-Recoverability of Reed–Solomon Codes via Tree Packings, SIAM Journal on Computing 53(2):389–430 (2024), DOI 10.1137/21M1463707, preprint arXiv:2011.04453, https://doi.org/10.1137/21M1463707
  4. Eitan Goldberg, Chong Shangguan, Itzhak Tamo, List-Decoding and List-Recovery of Reed-Solomon Codes Beyond the Johnson Radius for Any Rate, preprint arXiv:2105.14754 (2021), https://arxiv.org/abs/2105.14754
  5. Joshua Brakensiek, Sivakanth Gopi, Visu Makam, Generic Reed-Solomon Codes Achieve List-Decoding Capacity, STOC 2023, DOI 10.1145/3564246.3585128, preprint arXiv:2206.05256, https://doi.org/10.1145/3564246.3585128
  6. Omar Alrabiah, Zeyu Guo, Venkatesan Guruswami, Ray Li, Zihan Zhang, Random Reed-Solomon Codes Achieve List-Decoding Capacity With Linear-Sized Alphabets, Advances in Combinatorics 2025:8, DOI 10.19086/aic.2025.8, preprint arXiv:2304.09445, https://doi.org/10.19086/aic.2025.8
  7. Zeyu Guo, Zihan Zhang, Randomly Punctured Reed-Solomon Codes Achieve the List Decoding Capacity over Polynomial-Size Alphabets, FOCS 2023, DOI 10.1109/FOCS57990.2023.00019, preprint arXiv:2304.01403 (withdrawn; merged into arXiv:2304.09445), https://arxiv.org/abs/2304.01403
  8. Joshua Brakensiek, Manik Dhar, Sivakanth Gopi, Zihan Zhang, AG Codes Achieve List-Decoding Capacity over Constant-Sized Fields, IEEE Transactions on Information Theory (to appear), preprint arXiv:2310.12898, https://arxiv.org/abs/2310.12898
  9. Yeyuan Chen, Zihan Zhang, Explicit Folded Reed-Solomon and Multiplicity Codes Achieve Relaxed Generalized Singleton Bounds, STOC 2025, preprint arXiv:2408.15925, https://arxiv.org/abs/2408.15925
  10. Fernando Granha Jeronimo, Tushant Mittal, Shashank Srivastava, Madhur Tulsiani, Explicit Codes Approaching Generalized Singleton Bound Using Expanders, STOC 2025, preprint arXiv:2502.07308, https://arxiv.org/abs/2502.07308
  11. Amit Berman, Yaron Shany, Itzhak Tamo, Explicit Subcodes of Reed-Solomon Codes That Efficiently Achieve List Decoding Capacity, IEEE Transactions on Information Theory (2025), DOI 10.1109/TIT.2025.3575899, https://doi.org/10.1109/TIT.2025.3575899
  12. Joshua Brakensiek, Yeyuan Chen, Manik Dhar, Zihan Zhang, From Random to Explicit via Subspace Designs With Applications to Local Properties and Matroids, preprint arXiv:2510.13777 (2025), https://arxiv.org/abs/2510.13777
  13. Joshua Brakensiek, Yeyuan Chen, Aaron Putterman, Zihan Zhang, Kai Zhe Zheng, Algorithmic List Decoding of Reed-Solomon Codes up to Capacity, preprint arXiv:2609.08005 (2026), https://arxiv.org/abs/2609.08005
  14. Fernando Granha Jeronimo, Algorithmic List Decoding at Capacity and Optimal Proximity Gaps for Reed-Solomon Codes, preprint arXiv:2609.05870 (2026), https://arxiv.org/abs/2609.05870