List-decoding and list-recovery of Reed-Solomon codes beyond the Johnson radius for any rate
Eitan Goldberg, Chong Shangguan, Itzhak Tamo · arXiv (Cornell University) · 2021
Understanding the limits of list-decoding and list-recovery of Reed-Solomon (RS) codes is of prime interest in coding theory and has attracted a lot of attention in recent decades. However, the best possible parameters for these problems are still unknown, and in this paper, we take a step in this direction. We show the existence of RS codes that are list-decodable or list-recoverable beyond the Johnson radius for \\emph{any} rate, with a polynomial field size in the block length. In particular, we show that for any $\\epsilon\\in (0,1)$ there exist RS codes that are list-decodable from radius $1-\\epsilon$ and rate less than $\\frac{\\epsilon}{2-\\epsilon}$, with constant list size. We deduce our results by extending and strengthening a recent result of Ferber, Kwan, and Sauermann on puncturing codes with large minimum distance and by utilizing the underlying code's linearity.