Deterministic methods improve Reed-Solomon error correction codes beyond limits
Deterministic Constructions of Reed-Solomon Codes Beyond the Johnson Bound
Computational Complexity
Summary
Reed-Solomon codes are a way to detect and fix errors in data, like when files get corrupted. Usually, there is a known limit called the Johnson bound on how many errors these codes can fix efficiently. The authors found a way to build these codes deterministically (with a fixed method rather than randomness) so they can fix even more errors than before, while still being practical to construct. Their approach uses connections to other mathematical problems and runs in reasonable time for large data sizes.
What this means in practice
- •For data storage engineers: Build storage systems with improved error correction that reliably recover data despite higher error rates using deterministically constructed Reed-Solomon codes beyond traditional limits.
- •For communication system designers: Design communication protocols that handle more transmission errors with predictable and efficiently constructed error-correcting codes, improving data integrity over noisy channels.
A theory result. No direct application yet.
Authors
Abhranil Chatterjee, Sumanta Ghosh, Zeyu Guo, Rohit Gurjar, Roshan Raj
Abstract
We give a deterministic quasipolynomial-time construction of Reed-Solomon codes that are list-decodable beyond the Johnson radius. Specifically, for every $ε\in(0,1]$ and all sufficiently large $n$, we construct an $[n,k]$ Reed-Solomon code of rate $R=Ω(ε/(1+\log(1/ε)))$ over a field of size $(nk)^{quasi-poly(nk)}$ that is $(1-ε,O(1/ε))$ list-decodable. The construction runs in quasi-poly(nk) time. We also give a deterministic construction of $[n,k]$-MDS$(3)$ Reed-Solomon codes for all integers $1\leq k<n$, with the same asymptotic bounds on field size and construction time. In the constant-rate regime, our field-size bound substantially improves the bound of $O(n^{k^{2k}})$ achieved by Roth's construction (Roth, IEEE TIT 2022). Our constructions exploit a connection to polynomial identity testing for read-once determinants, together with the quasipolynomial isolating-weight construction of Gurjar and Thierauf for linear matroid intersection (Gurjar and Thierauf, STOC 2017 and Computational Complexity 2020).