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 α₁,...,α_n from a field, and n subsets S₁... S_n of each of size at most ℓ, the list decoding algorithm of Guruswami and Sudan can in polynomial time output all polynomials p of degree at most k that satisfy p(α_i) ∈ S_i for every i, as long as ℓ < ⌈ n/k⌉. We show that the performance of this algorithm is the best possible in a strong sense; specifically, when ℓ = ⌈ n/k⌉, the list of output polynomials can be superpolynomially large in n. 2) For Reed-Solomon codes of block length n and dimension k + 1 where k = n^δ for small enough δ, we exhibit an explicit received word with a superpolynomial number of Reed-Solomon codewords that agree with it on (2 - ∈)k locations, for any desired ∈ > 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.