New error correcting codes from lifting
Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2015.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2015
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/99776 |
| _version_ | 1826208634421379072 |
|---|---|
| author | Guo, Alan Xinyu |
| author2 | Madhu Sudan. |
| author_facet | Madhu Sudan. Guo, Alan Xinyu |
| author_sort | Guo, Alan Xinyu |
| collection | MIT |
| description | Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2015. |
| first_indexed | 2024-09-23T14:08:24Z |
| format | Thesis |
| id | mit-1721.1/99776 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T14:08:24Z |
| publishDate | 2015 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/997762019-04-11T12:26:56Z New error correcting codes from lifting Guo, Alan Xinyu Madhu Sudan. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2015. This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. Cataloged from student-submitted PDF version of thesis. Includes bibliographical references (pages 117-121). Error correcting codes have been widely used for protecting information from noise. The theory of error correcting codes studies the range of parameters achievable by such codes, as well as the efficiency with which one can encode and decode them. In recent years, attention has focused on the study of sublinear-time algorithms for various classical problems, such as decoding and membership verification. This attention was driven in part by theoretical developments in probabilistically checkable proofs (PCPs) and hardness of approximation. Locally testable codes (codes for which membership can be verified using a sublinear number of queries) form the combinatorial core of PCP constructions and thus play a central role in computational complexity theory. Historically, low-degree polynomials (the Reed-Muller code) have been the locally testable code of choice. Recently, "affine-invariant" codes have come under focus as providing potential for new and improved codes. In this thesis, we exploit a natural algebraic operation known as "lifting" to construct new affine-invariant codes from shorter base codes. These lifted codes generically possess desirable combinatorial and algorithmic properties. The lifting operation preserves the distance of the base code. Moreover, lifted codes are naturally locally decodable and testable. We tap deeper into the potential of lifted codes by constructing the "lifted Reed-Solomon code", a supercode of the Reed-Muller code with the same error-correcting capabilities yet vastly greater rate. The lifted Reed-Solomon code is the first high-rate code known to be locally decodable up to half the minimum distance, locally list-decodable up to the Johnson bound, and robustly testable, with robustness that depends only on the distance of the code. In particular, it is the first high-rate code known to be both locally decodable and locally testable. We also apply the lifted Reed-Solomon code to obtain new bounds on the size of Nikodym sets, and also to show that the Reed-Muller code is robustly testable for all field sizes and degrees up to the field size, with robustness that depends only on the distance of the code. by Alan Xinyu Guo. Ph. D. 2015-11-09T19:12:22Z 2015-11-09T19:12:22Z 2015 2015 Thesis http://hdl.handle.net/1721.1/99776 927331774 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 121 pages application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Guo, Alan Xinyu New error correcting codes from lifting |
| title | New error correcting codes from lifting |
| title_full | New error correcting codes from lifting |
| title_fullStr | New error correcting codes from lifting |
| title_full_unstemmed | New error correcting codes from lifting |
| title_short | New error correcting codes from lifting |
| title_sort | new error correcting codes from lifting |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/99776 |
| work_keys_str_mv | AT guoalanxinyu newerrorcorrectingcodesfromlifting |