Subspace Polynomials and Limits to List Decoding of Reed–Solomon Codes

摘要

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 FN, |FN| = N, for any ¿ ¿ (0,1), and K = N¿: (1) Existence: there exists a received word wN : FN ¿ FN 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 : FN ¿ FN 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.