Limits to list decoding Reed-Solomon codes

In this paper, we prove the following two results that expose some combinatorial limitations to list decoding Reed-Solomon codes. Given n distinct elements α 1 ,...,α n from a field F, and n subsets S 1 ,...,S n of F each of size at most l, the list decoding algorithm of Guruswami and Sudan [7] can in polynomial time output all polynomials p of degree at most k which satisfy p(α i ) ∈ S i for every i, as long as l √k n'. By our result, an improvement to the Reed-Solomon list decoder of [7] that works with slightly smaller agreement, say t > √kn' - k/2, can only be obtained by exploiting some property of the β i 's (for example, their (near) distinctness).

Authors

• Venkatesan Guruswami
• Atri Rudra

Keywords

• BCH codes
• Johnson bound
• Reed-Solomon codes
• list decoding
• list recovering