{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/99776"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/99776","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"New error correcting codes from lifting","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Guo, Alan Xinyu"],"institution":"Massachusetts Institute of Technology","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science.","school":null,"contributors":[],"advisors":["Madhu Sudan."],"committee_chairs":[],"committee_members":[],"year":2015,"date_issued":"2015","date_published":"2015","updated_at":"2026-07-22T22:21:59Z","subjects":["Electrical Engineering and Computer Science."],"languages":["eng"],"rights":["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."],"rights_urls":["http://dspace.mit.edu/handle/1721.1/7582"],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/1721.1/99776","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Madhu Sudan."]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science."]},{"key":"dc:contributor.other","label":"Dc Contributor Other","values":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science."]},{"key":"dc:creator","label":"Author","values":["Guo, Alan Xinyu"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2015-11-09T19:12:22Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2015-11-09T19:12:22Z"]},{"key":"dc:date.issued","label":"Date","values":["2015"]},{"key":"dc:publisher","label":"Institution","values":["Massachusetts Institute of Technology"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Electrical Engineering and Computer Science."]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["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."]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://dspace.mit.edu/handle/1721.1/7582"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/1721.1/99776"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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)."]},{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["Ph. D."]},{"key":"dc:title","label":"Title","values":["New error correcting codes from lifting"]}]}],"canonical_facts":{"dc:contributor.advisor":["Madhu Sudan."],"dc:contributor.department":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science."],"dc:contributor.other":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science."],"dc:creator":["Guo, Alan Xinyu"],"dc:date.accessioned":["2015-11-09T19:12:22Z"],"dc:date.available":["2015-11-09T19:12:22Z"],"dc:date.issued":["2015"],"dc:description":["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)."],"dc:description.abstract":["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."],"dc:description.degree":["Ph. D."],"dc:identifier.uri":["http://hdl.handle.net/1721.1/99776"],"dc:language.iso":["eng"],"dc:publisher":["Massachusetts Institute of Technology"],"dc:rights":["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."],"dc:rights.uri":["http://dspace.mit.edu/handle/1721.1/7582"],"dc:subject":["Electrical Engineering and Computer Science."],"dc:title":["New error correcting codes from lifting"],"dc:type":["Thesis"]},"updated_at":"2026-07-22T22:21:59Z"}