Subspace polynomials and list decoding of Reed-Solomon codes
Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, February 2007.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2007
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/38667 |
| _version_ | 1826218158734704640 |
|---|---|
| author | Kopparty, Swastik |
| author2 | Madhu Sudan. |
| author_facet | Madhu Sudan. Kopparty, Swastik |
| author_sort | Kopparty, Swastik |
| collection | MIT |
| description | Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, February 2007. |
| first_indexed | 2024-09-23T17:15:25Z |
| format | Thesis |
| id | mit-1721.1/38667 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T17:15:25Z |
| publishDate | 2007 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/386672019-04-11T07:42:59Z Subspace polynomials and list decoding of Reed-Solomon codes Kopparty, Swastik Madhu Sudan. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, February 2007. Includes bibliographical references (p. 29-31). 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 any ... , there exist arbitrarily large fields ... * Existence: there exists a received word ... that agrees with a super-polynomial number of distinct degree K polynomials on ... points each; * Explicit: there exists a polynomial time constructible received word ... that agrees with a super-polynomial number of distinct degree K polynomials, on ... points each. Ill both cases, our results improve upon the previous state of the art, which was , NM/6 for the existence case [JH01], and a ... for the explicit one [GR,05b]. Furthermore, for 6 close to 1 our bound approaches the Guruswami-Sudan bound (which is ... ) and rules out the possibility of extending their efficient RS list decoding algorithm to any significantly 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. (cont.) These subspace polynomials are a subclass of linearized polynomials that were studied by Ore [Ore33, Ore34] in the 1930s and by coding theorists. For us their main attraction is their sparsity and abundance of roots. We also complement our negative results by giving a list decoding algorithm for linearized polynomials beyond the Johnson-Guruswami-Sudan bounds. by Swastik Kopparty. S.M. 2007-08-29T20:41:44Z 2007-08-29T20:41:44Z 2006 2007 Thesis http://hdl.handle.net/1721.1/38667 163581865 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 31 leaves application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Kopparty, Swastik Subspace polynomials and list decoding of Reed-Solomon codes |
| title | Subspace polynomials and list decoding of Reed-Solomon codes |
| title_full | Subspace polynomials and list decoding of Reed-Solomon codes |
| title_fullStr | Subspace polynomials and list decoding of Reed-Solomon codes |
| title_full_unstemmed | Subspace polynomials and list decoding of Reed-Solomon codes |
| title_short | Subspace polynomials and list decoding of Reed-Solomon codes |
| title_sort | subspace polynomials and list decoding of reed solomon codes |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/38667 |
| work_keys_str_mv | AT koppartyswastik subspacepolynomialsandlistdecodingofreedsolomoncodes |