Improvements on the Johnson bound for Reed–Solomon codes

For Reed–Solomon codes with block length nn and dimension kk, the Johnson theorem states that for a Hamming ball of radius smaller than n−nk, there can be at most O(n2)O(n2) codewords. It was not known whether for larger radius, the number of codewords is polynomial. The best known list decoding algorithm for Reed–Solomon codes due to Guruswami and Sudan [Venkatesan Guruswami, Madhu Sudan, Improved decoding of Reed–Solomon and algebraic-geometry codes, IEEE Transactions on Information Theory 45 (6) (1999) 1757–1767] is also known to work in polynomial time only within this radius. In this paper we prove that when k<αnk<αn for any constant 0<α<10<α<1, we can overcome the barrier of the Johnson bound for list decoding of Reed–Solomon codes (even if the field size is exponential). More specifically in such a case, we prove that for Hamming ball of radius n−nk+c (for any c>0c>0) there can be at most O(nc2α(1−α)2+c+2) number of codewords. For any constant cc, we describe a polynomial time algorithm for enumerating all of them, thereby also improving on the Guruswami–Sudan algorithm. Although the improvement is modest, this provides evidence for the first time that the n−nk bound is not sacrosanct for such a high rate.We apply our method to obtain sharper bounds on a list recovery problem introduced by Guruswami and Rudra [Venkatesan Guruswami, Atri Rudra, Limits to list decoding Reed–Solomon codes, IEEE Transactions on Information Theory 52 (8) (2006) 3642–3649] where they establish super-polynomial lower bounds on the output size when the list size exceeds ⌈nk⌉. We show that even for larger list sizes the problem can be solved in polynomial time for certain values of kk.