Reed solomon codes achieve optimal error correction with explicit construction
Explicit Reed-Solomon Subspace Designs: Optimal List and Line Decoding
Information TheoryComputational Complexity
Summary
Reed-Solomon codes help fix errors in digital data, but fixing lots of errors usually means dealing with many possible solutions. The authors figured out a way to explicitly pick special points for these codes that lets you fix nearly the maximum number of errors while keeping the number of possible solutions small and manageable. They also created efficient methods to decode these codes quickly. This improves on previous methods by making the problem easier to solve without losing error-correcting power.
What this means in practice
- •For network engineers: Improve data transmission reliability by using Reed-Solomon codes with optimal error correction and manageable decoding complexity over large fields.
- •For storage system developers: Develop storage devices with enhanced error correction that balance high data rates and efficient error recovery using explicitly constructed codes.
Authors
Omar Alrabiah, Rohan Goyal, Venkatesan Guruswami
Abstract
For any desired rate $R \in (0,1)$, and gap to list-decoding capacity $\varepsilon > 0$, we give an explicit $n^{O_{\varepsilon}(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-\varepsilon$ of errors with the optimal list-size of $O(\frac{1-R}{\varepsilon})$. 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-\varepsilon$ errors with list size $(1/\varepsilon)^{O(1/\varepsilon)}$. We provide a deterministic list-decoding algorithm for both constructions running in time $O_ε(1)\mathsf{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.