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

Eli Ben-Sasson, Swastik Kopparty, Jaikumar Radhakrishnan

Research output: Contribution to journalArticle

13 Scopus citations

Abstract

We show combinatorial limitations on efficient list decoding of Reed-Solomon codes beyond the Johnson-Guruswami-Sudan bounds. In particular, we show that 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 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 √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.

Original languageEnglish (US)
Article number5361468
Pages (from-to)113-120
Number of pages8
JournalIEEE Transactions on Information Theory
Volume56
Issue number1
DOIs
StatePublished - Jan 1 2010

    Fingerprint

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Keywords

  • Guruswami-Sudan algorithm
  • Johnson bound
  • List decoding
  • Reed-Solomon codes
  • Subspace polynomials

Cite this