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. 1) Given n distinct elements alpha(1),...,alpha(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 can in polynomial time output all polynomials p of degree at most k that satisfy p (alpha(i)) epsilon S-i for every i, as long as l < [n/k]. We show that the performance of this algorithm is the best possible in a strong sense; specifically, when l = [n/k], the list of output polynok mials can be superpolynomially large in n. 2) For Reed-Solomon codes of block length n and dimension k + 1 where k = n(delta) for small enough delta, we exhibit an explicit received word with a superpolynomial number of Reed-Solomon codewords that agree with it on (2 - epsilon)k locations, for any desired epsilon > 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.