
Research
Abstracts  2007 
Limits to List Decoding ReedSolomon CodesEli BenSasson, Swastik Kopparty & Jaikumar RadhakrishnanA fundamental task associated with the use of errorcorrecting codes is {\em decoding,} that is, recovering the original codeword $w$, from the corrupted received word $w'$. In {\em list decoding}, introduced independently by Elias and Wozencraft, we consider a relaxation of the above task. We no longer demand that the codeword $w$ be recovered uniquely. Instead, we ask for a of possible codewords, and we call the recovery successful if $w$ appears in this list. The crucial point is that list decoding (with relatively small lists) is possible even when the received word's agreement with the original word is so small that any hope of recovering the original word uniquely is unrealistic. Clearly, the size of the list is a crucial parameter of the problem (to wit, the set of all codewords is a trivial solution for unbounded list size). In order to quantify the number of errors one can tolerate for list decoding and appreciate the difference with unique decoding, let us consider a code with block length $N$ and distance $d$. Suppose the number of errors in the transmission is guaranteed to be at most $e$. Then, in the worst case, we can uniquely recover the original message only if $e$ is at most $\frac{d1}{2}$. Thus, even if $d$ is very close to $N$, we require that the two words agree on at least $N  \frac{d1}{2} \geq \frac{N}{2}$ places. With list decoding we can, in principle, tolerate substantially more errors. \begin{theorem}[Johnson bound \cite{Johnson,Johnson1,GuruswamiSudanJB}] Let ${\cal C}$ be a code with block length $N$ and distance $d$. Then, the number of codewords that agree with any word $w'$ on more than $\sqrt{N(Nd)}$ places is $O(N^2)$. \end{theorem} For example, if the code has distance $0.99N$, then there are only a polynomial number of words that agree with the given word on more than $\frac{N}{10}$ places, that is, we have polynomial size lists as long as the error is less than $0.9N$. In fact, a more precise form of the Johnson bound~\cite{GuruswamiSudanJB} implies that if the error is less than $0.8N$, then there are only a constant number of such codewords. In contrast, unique decoding is feasible only when the error is guaranteed to be less than $0.495N$. Given a specific family of codes (in this paper, we shall consider ReedSolomon codes), we recall two fundamental problems associated with list decoding:
In order to solve the algorithmic list decoding problem (for a specific code ${\cal{C}}$ and agreement parameter $A$) in worstcase time $T$, at the very least we should have a combinatorial guarantee that there are no more than $T$ codewords in the list. In other words, lower bounds for the combinatorial problem imply lower bounds for the algorithmic one. Our main result is an improved lower bound for the combinatorial list decoding problem for ReedSolomon codes (described next). This result implies superpolynomial lower bounds on the running time of any list decoding algorithm for ReedSolomon codes for a sufficiently small agreement parameter. References:[1] Eli BenSasson, Swastik Kopparty and Jaikumar Radhakrishnan. Subspace polynomials and List Decoding of ReedSolomon Codes. In Proceedings of FOCS 2006, Berkeley, CA, 2006. 

