Limits to List Decoding Reed–Solomon Codes
Venkatesan Guruswami, Atri Rudra · IEEE Transactions on Information Theory · 2006
In this paper, we prove the following two results that expose some combinatorial limitations to list decoding Reed-Solomon codes. 1) Given n distinct elements alpha1,...,alphanfrom a field F, and n subsets S1,...,Snof F, each of size at most l, the list decoding algorithm of Guruswami and Sudan can in polynomial time output all polynomials p of degree at most k that satisfy p(alphai)isinSifor every i, as long as ldeltafor small enough delta, we exhibit an explicit received word with a superpolynomial number of Reed-Solomon codewords that agree with it on (2-epsi)k locations, for any desired epsi>0 (agreement of k is trivial to achieve). Such a bound was known earlier only for a nonexplicit center. Finding explicit bad list decoding configurations is of significant interest-for example, the best known rate versus distance tradeoff, due to Xing, is based on a bad list decoding configuration for algebraic-geometric codes, which is unfortunately not explicitly known