Efficient list-decoding of Reed-Solomon codes at the generalized Singleton radius, and efficient certification of optimal list-decodability

Shangguan and Tamo (STOC 2020) proved that Reed-Solomon (RS) codes over sufficiently large finite fields attain the generalized Singleton bound for list-decoding with list sizes $L=2$ and $L=3$, giving the first explicit RS codes combinatorially list-decodable beyond the Johnson radius; Brakensiek, Gopi, and Makam (STOC 2023) later resolved the full conjecture for every list size, and Alrabiah, Guruswami, and Li showed that exponentially large alphabets are necessary for this optimal trade-off. What remains open — restated as Question 1.26 in the Brakensiek-Gopi-Makam paper, there under the stronger average-radius form of attainment — is the algorithmic realization of this combinatorial theory: (i) given an $[n,k]$ RS code promised to attain the generalized Singleton bound (e.g., the explicit tower-of-extensions construction of Shangguan-Tamo) and a received word, list all codewords within the optimal radius $\frac{L}{L+1}(n-k)$ using a number of field operations polynomial in $n$ and independent of the (possibly exponentially large) field size; and (ii) given an evaluation vector, decide in $\operatorname{poly}(n)$ field operations whether the corresponding RS code attains the bound for $L=2$ or $L=3$.

Background

A Reed-Solomon (RS) code is a classical algebraic error-correcting code: fixing a finite field $\mathbb{F}_q$, a dimension $k$, and $n$ distinct evaluation points $\alpha_1,\dots,\alpha_n\in\mathbb{F}_q$, the $[n,k]$ RS code consists of all codewords $(f(\alpha_1),\dots,f(\alpha_n))$ obtained from polynomials $f$ of degree less than $k$. A code is $(\rho,L)$-list-decodable if every Hamming ball of radius $\rho n$ contains at most $L$ codewords; this allows error correction well beyond the $n/2$ unique-decoding barrier. The Johnson bound guarantees that any code of rate $R=k/n$ is $(1-\sqrt{R},\,\mathrm{poly})$-list-decodable, and the celebrated Guruswami-Sudan algorithm efficiently list-decodes any RS code up to this Johnson radius (Guruswami and Sudan, 1999). Whether RS codes are list-decodable — even combinatorially — beyond the Johnson radius was a major open question, affirmatively settled for random RS codes over very large fields in order-of-magnitude form by Rudra and Wootters (2014). Shangguan and Tamo (2020) then determined the exact optimal trade-off: they proved a generalized Singleton bound stating that a linear $[n,k]$ code that is $(\rho,L)$-list-decodable over an alphabet larger than $L$ must satisfy $\rho\le\frac{L}{L+1}(1-R)$, and showed that for $L=2$ and $L=3$ almost all $[n,k]$ RS codes over sufficiently large fields attain this bound with equality, in particular beating the Johnson radius for rates above $1/4$ (for $L=2$) and $1/9$ (for $L=3$). Their existence proofs require fields of size exponential in $n$, and they gave an explicit construction for $L=2$ over a field of double-exponential size, built from a tower of field extensions $\mathbb{F}_{2^{k_{i-1}}}(\alpha_i)=\mathbb{F}_{2^{k_i}}$ of degree $k$ at each evaluation point. The combinatorial picture was completed by Brakensiek, Gopi, and Makam (2023), who proved the conjecture of Shangguan-Tamo in full: generic RS codes, and random RS codes over fields of exponential size, are list-decodable (even in the stronger average-radius sense, where the average distance of the $L+1$ codewords from the center, not just each individual distance, must exceed the radius) with list size $L$ up to exactly $\frac{L}{L+1}(1-R)$, for every $L$; their framework connects the problem to higher-order MDS codes (Roth, 2022), which generalize the classical MDS property (a linear code attaining the ordinary Singleton bound $d\le n-k+1$). Alrabiah, Guruswami, and Li then proved that approaching the generalized Singleton bound for any fixed $L>1$ requires alphabets of size $\exp(\Omega(1/\varepsilon))$ where $\varepsilon$ is the gap to the bound, so the exponential field size is essential, not an artifact; over fields of linear size $O(n)$, random RS codes still achieve list-decoding capacity $1-R-\varepsilon$ but only with polynomial-size lists (Alrabiah, Guo, Guruswami, Li, and Zhang, 2024). One subtlety drives the algorithmic question: when the field size $q$ is exponential in $n$, an algorithm using $\operatorname{poly}(n)$ field operations is sublinear even in the bit-length of the received word, so the natural information-set decoding attack (enumerate $k$-subsets of coordinates and interpolate) already runs in only $n^{O(k)}$ field operations; the question, as posed by Shangguan-Tamo, is whether $\operatorname{poly}(n)$ field operations — measured independently of the field size — suffices to realize the provably optimal combinatorial list-decodability. All known efficient decoders for RS-type codes beyond the Johnson radius apply only to variants (folded RS codes, which evaluate each polynomial at overlapping batches of points; multiplicity codes, which record the polynomial together with its derivatives up to a fixed order at each point; and other polynomial ideal codes, the general family of algebraic codes obtained by evaluating polynomials modulo a fixed ideal) or to explicit subcodes, not to full RS codes.

Problem Statement

The problem is the algorithmic realization, for full Reed-Solomon codes, of the now-complete combinatorial theory of optimal list-decoding at the generalized Singleton bound. It comprises two linked deliverables sharing one objective — $\operatorname{poly}(n)$-field-operation algorithms, with complexity counted in arithmetic operations over $\mathbb{F}_q$ and independent of the field size $q$ — posed as items 1, 2, and 5 of the open-questions list in Shangguan-Tamo (STOC 2020) and restated as Question 1.26 of Brakensiek-Gopi-Makam for the decoding part, there under the stronger average-radius promise. Throughout this task, "attains the generalized Singleton bound for list size $L$" has the plain $(\frac{L}{L+1}(1-R),L)$-list-decoding sense formalized in (i) below; the stronger average-radius sense discussed in the Background and used by Brakensiek-Gopi-Makam implies this plain sense, so a code attaining the bound in the average-radius sense also attains it here.

(i) Decoding beyond the Johnson radius. Fix a constant list size $L\ge 2$ and integers $n>k\ge 1$ with rate $R=k/n$. Given an $[n,k]$ RS code $C$ over $\mathbb{F}_q$ (with $q$ possibly exponential or double-exponential in $n$) that is promised to attain the generalized Singleton bound for list size $L$, i.e., $C$ is $(\frac{L}{L+1}(1-R),L)$-list-decodable — for example the explicit tower-of-extensions construction of Shangguan-Tamo (Theorem 1.7) for $L=2$, or a generic/random RS code over a field of exponential size for any $L$ — and given a received word $y\in\mathbb{F}_q^n$, output every codeword $c\in C$ with Hamming distance at most $\frac{L}{L+1}(n-k)$ from $y$, using a number of field operations polynomial in $n$ — with the degree of the polynomial independent of $k$ — and independent of $q$. Alternatively, prove that no such algorithm exists; such a proof must rule out every algorithm meeting (i)'s field-operation budget — every decoder that uses $\operatorname{poly}(n)$ field operations over $\mathbb{F}_q$, with degree independent of $k$ — including those that exploit the evaluation-point structure of the code.

(ii) Certification of optimal list-decodability. Given $n$, $k$, and an evaluation vector $(\alpha_1,\dots,\alpha_n)$ of distinct elements of $\mathbb{F}_q$, decide using $\operatorname{poly}(n)$ field operations whether the $[n,k]$ RS code defined by this evaluation vector attains the generalized Singleton bound for $L=2$ (in the plain sense fixed above), and analogously for $L=3$.

The two deliverables are posed as separate items of the source open-questions list, but they ask the same underlying question — whether the provably optimal list-decodability of RS codes, which provably requires exponentially large alphabets, can be exploited or verified by algorithms whose arithmetic cost is polynomial in the block length alone.

References

1. Chong Shangguan and Itzhak Tamo, "Combinatorial list-decoding of Reed-Solomon codes beyond the Johnson radius", STOC 2020, DOI 10.1145/3357713.3384295; arXiv:1911.01502. https://arxiv.org/abs/1911.01502
2. Joshua Brakensiek, Sivakanth Gopi, and Visu Makam, "Generic Reed-Solomon Codes Achieve List-Decoding Capacity", STOC 2023; arXiv:2206.05256. https://arxiv.org/abs/2206.05256
3. Omar Alrabiah, Venkatesan Guruswami, and Ray Li, "AG codes have no list-decoding friends: Approaching the generalized Singleton bound requires exponential alphabets", SODA 2024 / IEEE Transactions on Information Theory 2025; arXiv:2308.13424. https://arxiv.org/abs/2308.13424
4. Omar Alrabiah, Zeyu Guo, Venkatesan Guruswami, Ray Li, and Zihan Zhang, "Random Reed-Solomon Codes Achieve List-Decoding Capacity With Linear-Sized Alphabets", STOC 2024; arXiv:2304.09445. https://arxiv.org/abs/2304.09445
5. Eitan Goldberg, Chong Shangguan, and Itzhak Tamo, "List-decoding and list-recovery of Reed-Solomon codes beyond the Johnson radius for any rate", IEEE Transactions on Information Theory 2023; arXiv:2105.14754. https://arxiv.org/abs/2105.14754
6. Eitan Goldberg, Chong Shangguan, and Itzhak Tamo, "Singleton-type bounds for list-decoding and list-recovery, and related results", Journal of Combinatorial Theory A 2024; arXiv:2112.05592. https://arxiv.org/abs/2112.05592
7. Noga Ron-Zewi, S. Venkitesh, and Mary Wootters, "Efficient List-decoding of Polynomial Ideal Codes with Optimal List Size", 2024; arXiv:2401.14517. https://arxiv.org/abs/2401.14517
8. Amit Berman, Yaron Shany, and Itzhak Tamo, "Explicit Subcodes of Reed-Solomon Codes that Efficiently Achieve List Decoding Capacity", IEEE International Symposium on Information Theory (ISIT) 2024; arXiv:2401.15034. https://arxiv.org/abs/2401.15034
9. Soham Chatterjee, Prahladh Harsha, and Mrinal Kumar, "Deterministic list decoding of Reed-Solomon codes", STOC 2026; arXiv:2511.05176. https://arxiv.org/abs/2511.05176
10. Ron M. Roth, "Higher-Order MDS Codes", IEEE Transactions on Information Theory 2022; arXiv:2111.03210. https://arxiv.org/abs/2111.03210
11. Asaf Ferber, Matthew Kwan, and Lisa Sauermann, "List-decodability with large radius for Reed-Solomon codes", FOCS 2021 / IEEE Transactions on Information Theory 2022; arXiv:2012.10584. https://arxiv.org/abs/2012.10584
12. Zeyu Guo, Ray Li, Chong Shangguan, Itzhak Tamo, and Mary Wootters, "Improved List-Decodability and List-Recoverability of Reed-Solomon Codes via Tree Packings", FOCS 2021 / SIAM Journal on Computing 2024; arXiv:2011.04453. https://arxiv.org/abs/2011.04453
13. Venkatesan Guruswami and Madhu Sudan, "Improved decoding of Reed-Solomon and algebraic-geometry codes", IEEE Transactions on Information Theory 45(6):1757-1767, 1999, DOI 10.1109/18.782097. https://doi.org/10.1109/18.782097
14. Atri Rudra and Mary Wootters, "Every list-decodable code for high noise has abundant near-optimal rate puncturings", STOC 2014, DOI 10.1145/2591796.2591797. https://doi.org/10.1145/2591796.2591797