|
List decoding for Reed-Solomon Codes Prof. Jaikumar Radhakrishnan TIFR, Mumbai. 08-01-07 Abstract We consider the list decoding problem for Reed-Solomon codes, where given a field ${\mathbb F}$ of size $N$, a word $w:{\mathbb F} \rightarrow {\mathbb F}$ and integers $a,d \geq 1$, we are required to list all polynomials of degree at most $d$ that agree with $w$ on at least $a$ points. Johnson's bound (1962) implies that if $a > \sqrt{Nd}$, then the list has at most $O(N^2)$ polynomials. In this case, an algorithm of Guruswami and Sudan (2000) can in fact produce the list in polynomial time. However, it is not known if Johnson's bound is tight or the list is of polynomial size even if we require significantly less than $\sqrt{Nd}$ agreements. For a range of parameters $a$ and $d$, we exhibit a word $w$ that agrees on $a$ points with a superpolynomial number of polynomials of degree $d$. We use polynomials that vanish on subspaces of an extension field, viewed as a vector space over a base field. (Joint work with Swastik Kopparty, MIT Cambridge, and Eli Ben-Sasson, Toyota Technological Institute at Chicago.)
|
