Subspace Polynomials and List Decoding of Reed-Solomon Codes Export

@inproceedings{SassonKoppartyRadhakrishnan:FOCS2006, 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 \mathbb{F}\_N ,|\mathbb{F}\_N| = N, for any \delta \in (0, 1), and K = N^{\delta}: --Existence: there exists a received word w\_N : \mathbb{F}\_N \to\mathbb{F}\_N that agrees with a super-polynomial number of distinct degree K polynomials on \approxN^{\sqrt \delta}points each;--Explicit: there exists a polynomial time constructible received word w'\_N: \mathbb{F}\_N \to \mathbb{F}\_N that agrees with a super-polynomial number of distinct degree K polynomials, on \approx 2^{\sqrt {\log N} } K points each. In both cases, our results improve upon the previous state of the art, which was \approx N^{\delta}/\delta for the existence case [JH01], and \approx 2N^{\delta} for the explicit one [GR05b]. Furthermore, for \delta close to 1 our bound approaches the Guruswami-Sudan bound (which is \sqrt {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 subspace 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].}, address = {Washington, DC, USA}, author = {Sasson, Eli B. and Kopparty, Swastik and Radhakrishnan, Jaikumar}, booktitle = {FOCS '06: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science}, citeulike-article-id = {5836128}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1170502}, citeulike-linkout-1 = {http://dx.doi.org/10.1109/FOCS.2006.73}, doi = {10.1109/FOCS.2006.73}, isbn = {0-7695-2720-5}, keywords = {list-decoding, reed-solomon}, pages = {207--216}, posted-at = {2009-09-24 17:17:34}, priority = {2}, publisher = {IEEE Computer Society}, title = {Subspace Polynomials and List Decoding of Reed-Solomon Codes}, url = {http://dx.doi.org/10.1109/FOCS.2006.73}, year = {2006} }

TY - CONF ID - SassonKoppartyRadhakrishnan:FOCS2006 L3 - citeulike-article-id:5836128 N2 - 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 \mathbb{F}_N ,|\mathbb{F}_N| = N, for any \delta \in (0, 1), and K = N^{\delta}: --Existence: there exists a received word w_N : \mathbb{F}_N \to\mathbb{F}_N that agrees with a super-polynomial number of distinct degree K polynomials on \approxN^{\sqrt \delta}points each;--Explicit: there exists a polynomial time constructible received word w'_N: \mathbb{F}_N \to \mathbb{F}_N that agrees with a super-polynomial number of distinct degree K polynomials, on \approx 2^{\sqrt {\log N} } K points each. In both cases, our results improve upon the previous state of the art, which was \approx N^{\delta}/\delta for the existence case [JH01], and \approx 2N^{\delta} for the explicit one [GR05b]. Furthermore, for \delta close to 1 our bound approaches the Guruswami-Sudan bound (which is \sqrt {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 subspace 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]. SN - 0-7695-2720-5 AD - Washington, DC, USA EP - 216 TI - Subspace Polynomials and List Decoding of Reed-Solomon Codes PB - IEEE Computer Society T2 - FOCS '06: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science SP - 207 KW - list-decoding KW - reed-solomon AU - Sasson, Eli AU - Kopparty, Swastik AU - Radhakrishnan, Jaikumar PY - 2006/// UR - http://dx.doi.org/10.1109/FOCS.2006.73 ER -