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 α ₁,...,αα ₁ from a field double-struck F sign, and n subsets S ₁,..., S _n of double-struck F sign 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(α ₁) ∈ 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, we show that when l = [n/k], the list of output polynomials can be super-polynomially large in n. One way to interpret our result is the following. The algorithm in [7] can, when given as input n distinct pairs (β _i, γ _i) ∈ double-struck F sign ² (the βi's need not be distinct), find and output all degree k polynomials p such that p(β _i) = γ _i for at least t values of i, provided t > √kn′. 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). 2. For Reed-Solomon codes of block length n and dimension k where k = n ^δ for small enough 5, we exhibit an explicit received word r with a super-polynomial number of Reed-Solomon codewords that agree with it on (2 - ε)k locations, for any desired ε > 0 (we note agreement of k is trivial to achieve). Such a bound was known earlier only for a non-explicit center. We remark that finding explicit bad list decoding configurations is of significant interest -for example the best known rate vs. distance trade-off is based on a bad list decoding configuration for algebraic-geometric codes [14] which is unfortunately not explicitly known.