Name
Abstract | ||
|---|---|---|
We show combinatorial limitations on efficient list decoding of Reed-Solomon codes beyond the Johnson-Guruswami-Sudan bounds. In particular,we showthat for arbitrarily large fields FN, |FN| = N, for any δ Ɛ, (0,1) and K = Nδ : • 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; • Explicit: there exists a polynomial time constructible received word w1N : FN → FN that agrees with a superpolynomial number of distinct degree K polynomials, on ≈ 2√logN 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 √NK) 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 subspace 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 matrixcodes. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1109/TIT.2009.2034780 | IEEE Transactions on Information Theory |
Keywords | Field | DocType |
larger decoding radius,logn k,existence case,subspace polynomial,reed-solomon code,bound approach,efficient reed-solomon list,distinct degree k polynomial,k polynomial,distinct degree,efficient list,reed solomon,polynomials,reed solomon code,polynomial time,list decoding,artificial intelligence,decoding | Discrete mathematics,Binary logarithm,Combinatorics,Subspace topology,Polynomial,Reed–Solomon error correction,Johnson bound,Decoding methods,List decoding,Time complexity,Mathematics | Journal |
Volume | Issue | ISSN |
56 | 1 | 0018-9448 |
Citations | PageRank | References |
11 | 1.19 | 14 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Eli Ben-Sasson | 1 | 1641 | 86.98 |
| Swastik Kopparty | 2 | 384 | 32.89 |
| Jaikumar Radhakrishnan | 3 | 1123 | 96.04 |