Subspace polynomials and list decoding of reed-solomon codes

Eli Ben-Sasson, Swastik Kopparty, Jaikumar Radhakrishnan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Scopus citations

Abstract

We show combinatorial limitations on efficient list decoding of Reed-Solomon codes beyond the Johnson and Guruswami-Sudan bounds [Joh62, Joh63, GS99]. In particular, we show that for arbitrarily large fields ℱN= |ℱN| = N, for any δ ε (0, 1), and K = Nδ: • Existence: there exists a received word w N : ℱN → ℱN 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 : ℱN → ℱN that agrees with a super-polynomial number of distinct degree K poly-nomials, on ≈ 2√log N K points each. In both cases, our results improve upon the previous state of the art, which was ≈ Nδ / δ for the existence case [JH01], and ≈ 2Nδ for the explicit one [GR05b]. Furthermore, for δ close to 1 our bound approaches the Guruswami-Sudan bound (which is √NK) and implies limitations on extending their efficient RS list decoding algorithm to larger decoding radius. Our proof method is surprisingly simple. We work with polynomials that vanish on subspaces of an extension field viewed as a vector space over the base field. These sub-space polynomials are a subclass of linearized polynomials that were first studied by Ore [Ore33, Ore34] in the 1930s, and later by coding theorists. For us their main attraction is their sparsity and abundance of roots, virtues that recently won them pivotal roles in probabilistically checkable proofs of proximity [BSGH+04, BSS05] and sub-linear proof verification [BSGH+ 05].

Original languageEnglish (US)
Title of host publication47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006
Pages207-214
Number of pages8
DOIs
StatePublished - 2006
Externally publishedYes
Event47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006 - Berkeley, CA, United States
Duration: Oct 21 2006Oct 24 2006

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)0272-5428

Other

Other47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006
Country/TerritoryUnited States
CityBerkeley, CA
Period10/21/0610/24/06

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint

Dive into the research topics of 'Subspace polynomials and list decoding of reed-solomon codes'. Together they form a unique fingerprint.

Cite this