Subspace polynomials and limits to list decoding of Reed-Solomon codes

Abstract

We show combinatorial limitations on efficient list decoding of Reed-Solomon codes beyond the Johnson-Guraswami-Sudan bounds. In particular, we show that for arbitrarily large fields F_N, |F_N| = N, for any ?? ?? (0,1), and K = N^??: (1) Existence: there exists a received word w_N : F_N ?? F_N that agrees with a super-polynomial number of distinct degree K polynomials on ?? N^???? points each; (2) Explicit: there exists a polynomial time constructible received word w'_N : F_N ?? F_N that agrees with a superpolynomial number of distinct degree K polynomials, on ??2^??(log N) K points each. In both cases, our results improve upon the previous state of the art, which was ?? N^??/?? points of agreement for the existence case (proved by Justesen and Hoholdt), and ?? 2N^?? points of agreement for the explicit case (proved by Guruswami and Rudra). Furthermore, for ?? close to 1 our bound approaches the Guruswami-Sudan bound (which is ??(N K)) and implies limitations on extending their efficient Reed-Solomon list decoding algorithm to larger decoding radius. Our proof is based on some remarkable properties of sub-space polynomials. Using similar ideas, we then present a family of low rate codes that are efficiently list-decodable beyond the Johnson bound. This leads to an optimal list-decoding algorithm for the family of matrix-codes.