Improvements on the Johnson bound for ReedSolomon codes
For ReedSolomon codes with block length n n and dimension k k , the Johnson theorem states that for a Hamming ball of radius smaller than n ? n k , there can be at most O(n2) O ( n 2 ) codewords. It was not known whether for larger radius, the number of codewords is polynomial. The best known list decoding algorithm for ReedSolomon codes due to Guruswami and Sudan [Venkatesan Guruswami, Madhu Sudan, Improved decoding of ReedSolomon and algebraic-geometry codes, IEEE Transactions on Information Theory 45 (6) (1999) 17571767] is also known to work in polynomial time only within this radius. In this paper we prove that when k 0 c > 0 ) there can be at most O ( n c 2 ? ( 1 ? ? ) 2 + c + 2 ) number of codewords. For any constant c c , we describe a polynomial time algorithm for enumerating all of them, thereby also improving on the GuruswamiSudan algorithm. Although the improvement is modest, this provides evidence for the first time that the n ? n k 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 ReedSolomon codes, IEEE Transactions on Information Theory 52 (8) (2006) 36423649] where they establish super-polynomial lower bounds on the output size when the list size exceeds ? n k ? . We show that even for larger list sizes the problem can be solved in polynomial time for certain values of k k .
list decodability reed solomom codes