Subspace Polynomials and List Decoding of Reed-Solomon Codes

We show combinatorial limitations on efficient list decoding of Reed-Solomon codes beyond the Johnson and Guruswami-Sudan bounds in the works of S.M. Johnson (1962, 1963) and V. Guruswami and M. Sudan (1999). In particular, we show that for arbitrarily large fields F_N, |F_N| - N, for any delta isin (0,1), and K = N^delta; : middot Existence: there exists a received word w_N : F_N rarr F_N that agrees with a super-polynomial number of distinct degree K polynomials on ap N^radicdelta points each; middot Explicit: there exists a polynomial time constructible received word w´_N : F_N rarr F_N that agrees with a super-polynomial number of distinct degree K polynomials, on ap 2^{radic(log N)} K points each. In both cases, our results improve upon the previous state of the art, which was ap N^delta/delta for the existence case in the work J. Justesen and T. Hoboldt (2001), and ap 2N^delta for the explicit one in the work of V. Guruswami and M. Sudan (2005). Furthermore, for delta close to 1 our bound approaches the Guruswami-Sudan bound (which is radicNK) and implies limitations on extending their efficient RS list decoding algorithm to larger decoding radius. Our proof method is surprisingly simple. We work with polynomials that vanish on subspaces of an extension field viewed as a vector space over the base field. These sub-space polynomials are a subclass of linearized polynomials that were first studied by O. Ore (1933, 1934) in the 1930s, and later by coding theorists. For us their main attraction is their sparsity and abundance of roots, virtues that recently won them pivotal roles in probabilistically checkable proofs of proximity in the works of E. Ben-Sasson et al. (2004) and E. Ben-Sasson and M. Sudan (2005) and sub-linear proof verification in the work of E. Ben-Sasson et al. (2005)