List-decoding and list-recovery of Reed-Solomon codes beyond the Johnson radius for any rate

05/31/2021
by   Eitan Goldberg, et al.
0

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 any rate, with a polynomial field size in the block length. In particular, we show that for any ϵ∈ (0,1) there exist RS codes that are list-decodable from radius 1-ϵ and rate less than ϵ/2-ϵ, 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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset