Limits to List Decoding Reed—Solomon Codes.

In this paper, we prove the following two results that expose some combinatorial limitations to list decoding Given n distinct elements α1,…,αn, from a field F, and n subsets S1,…Sn 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(αi] ϵ Si 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 polynomials can be superpolynomially large in n. 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. [ABSTRACT FROM AUTHOR]