Explicit Reed-Solomon Subspace Designs: Optimal List and Line Decoding
Abstract
For any desired rate R ∈ (0,1), and gap to list-decoding capacity ε > 0, we give an explicit nOε(1) time construction of Reed-Solomon codes over extension fields of size polynomial in the block length n that can be list-decoded from a fraction 1−R−ε of errors with the optimal list-size of O((1−R)/ε). We also give a simpler, strongly explicit construction of evaluation points for which the associated Reed-Solomon code can be list-decoded from 1−R−ε errors with list size (1/ε)O(1/ε). We provide a deterministic list-decoding algorithm for both constructions running in time Oε(1)poly(n). In fact, our Reed-Solomon codes are near-optimal subspace-design codes over a subfield. Via known results, this directly implies the combinatorial list-decoding guarantee, as well as near-optimal list-recovery bounds. We also present a new reduction showing that the subspace-design guarantee also implies line decoding over the extension field itself, which then yields proximity gaps and mutual correlated agreement up to proximity parameter approaching the optimal 1−R radius. Compared to the recent algorithm of Brakensiek, Chen, Putterman, Zhang, and Zheng (2026), which list decodes every Reed-Solomon code over prime fields up to capacity, our approach achieves constant (in fact, near-optimal) list size rather than a polynomially growing one, at the cost of carefully choosing the code's evaluation points. In a companion paper, we show that these respective restrictions are unavoidable.
Related
- Algorithmic List Decoding at Capacity and Optimal Proximity Gaps for Reed-Solomon Codes
- A Complete Characterization of q-Ary $2$-Designs in Doubly-Extended Reed-Solomon Codes
- Algorithmic List Decoding of Reed-Solomon Codes up to Capacity
- Reed-Solomon Codes at Capacity: Algorithmic List-Decoding and Proximity Gaps
- Insdel Reed-Solomon Decoding Algorithms up to the Half-Singleton Bound
BibTeX
@misc{alrabiah2026explicit,
title = {{Explicit Reed-Solomon Subspace Designs: Optimal List and Line Decoding}},
author = {Omar Alrabiah and Rohan Goyal and Venkatesan Guruswami},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.36215},
eprint = {2610.36215},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.36215},
note = {CC BY-NC-SA 4.0},
}
RIS
TY - UNPB
TI - Explicit Reed-Solomon Subspace Designs: Optimal List and Line Decoding
AU - Omar Alrabiah
AU - Rohan Goyal
AU - Venkatesan Guruswami
PY - 2026
DA - 2026/10/26
PB - arXiv
DO - 10.48550/arxiv.2610.36215
UR - https://arxiv.org/abs/2610.36215
AB - For any desired rate R ∈ (0,1), and gap to list-decoding capacity ε > 0, we give an explicit n^O_ε(1) time construction of Reed-Solomon codes over extension fields of size polynomial in the block length n that can be list-decoded from a fraction 1−R−ε of errors with the optimal list-size of O((1−R)/ε). We also give a simpler, strongly explicit construction of evaluation points for which the associated Reed-Solomon code can be list-decoded from 1−R−ε errors with list size (1/ε)^O(1/ε). We provide a deterministic list-decoding algorithm for both constructions running in time O_ε(1)poly(n). In fact, our Reed-Solomon codes are near-optimal subspace-design codes over a subfield. Via known results, this directly implies the combinatorial list-decoding guarantee, as well as near-optimal list-recovery bounds. We also present a new reduction showing that the subspace-design guarantee also implies line decoding over the extension field itself, which then yields proximity gaps and mutual correlated agreement up to proximity parameter approaching the optimal 1−R radius. Compared to the recent algorithm of Brakensiek, Chen, Putterman, Zhang, and Zheng (2026), which list decodes every Reed-Solomon code over prime fields up to capacity, our approach achieves constant (in fact, near-optimal) list size rather than a polynomially growing one, at the cost of carefully choosing the code's evaluation points. In a companion paper, we show that these respective restrictions are unavoidable.
ER -