NDLI: Subspace Polynomials and List Decoding of Reed-Solomon Codes

Content Provider	IEEE Xplore Digital Library
Author	Ben-Sasson, E. Kopparty, S. Radhakrishnan, J.
Copyright Year	2006
Description	Author affiliation: Dept. of Comput. Sci., Technion-Israel Inst. of Technol., Haifa (Ben-Sasson, E.)
Abstract	We show combinatorial limitations on efficient list decoding of Reed-Solomon codes beyond the Johnson and Guruswami-Sudan bounds in the works of S.M. Johnson (1962, 1963) and V. Guruswami and M. Sudan (1999). In particular, we show that for arbitrarily large fields $F_{N},$ $\|F_{N}\|$ - N, for any delta isin (0,1), and K = Ndelta; : middot Existence: there exists a received word $w_{N}$ : $F_{N}$ rarr $F_{N}$ that agrees with a super-polynomial number of distinct degree K polynomials on ap Nradicdelta points each; middot Explicit: there exists a polynomial time constructible received word $w'_{N}$ : $F_{N}$ rarr $F_{N}$ that agrees with a super-polynomial number of distinct degree K polynomials, on ap 2radic(log N) K points each. In both cases, our results improve upon the previous state of the art, which was ap $N^{delta}/delta$ for the existence case in the work J. Justesen and T. Hoboldt (2001), and ap $2N^{delta}$ for the explicit one in the work of V. Guruswami and M. Sudan (2005). Furthermore, for delta close to 1 our bound approaches the Guruswami-Sudan bound (which is radicNK) 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 O. Ore (1933, 1934) 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 in the works of E. Ben-Sasson et al. (2004) and E. Ben-Sasson and M. Sudan (2005) and sub-linear proof verification in the work of E. Ben-Sasson et al. (2005)
Starting Page	207
Ending Page	216
File Size	280061
Page Count	10
File Format	PDF
ISBN	0769527205
ISSN	02725428
DOI	10.1109/FOCS.2006.73
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2006-10-21
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Decoding Reed-Solomon codes Polynomials Computer science Councils Career development Computer errors
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in