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

Ben-Sasson, E. ; Kopparty, S. ; Radhakrishnan, J. (2010) Subspace polynomials and limits to list decoding of Reed-Solomon codes IEEE Transactions on Information Theory, 56 (1). pp. 113-120. ISSN 0018-9448

Full text not available from this repository.

Official URL: http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumb...

Related URL: http://dx.doi.org/10.1109/TIT.2009.2034780

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 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.

Item Type:Article
Source:Copyright of this article belongs to IEEE.
ID Code:89497
Deposited On:27 Apr 2012 13:41
Last Modified:27 Apr 2012 13:41

Repository Staff Only: item control page