{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/79229"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/79229","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"Some closure features of locally testable affine-invariant properties","abstract":"We prove that the class of locally testable affine-invariant properties is closed under sums, intersections and \"lifts\". The sum and intersection are two natural operations on linear spaces of functions, where the sum of two properties is simply their sum as a vector space. The \"lift\" is a less well-studied property, which creates some interesting affine-invariant properties over large domains, from properties over smaller domains. Previously such results were known for \"single-orbit characterized\" affine-invariant properties, which are known to be a subclass of locally testable ones, and are potentially a strict subclass. The fact that the intersection of locally-testable affine-invariant properties are locally testable could have been derived from previously known general results on closure of property testing under set-theoretic operations, but was not explicitly observed before. The closure under sum and lifts is implied by an affirmative answer to a central question attempting to characterize locally testable affine-invariant properties, but the status of that question remains wide open. Affine-invariant properties are clean abstractions of commonly studied, and extensively used, algebraic properties such linearity and low-degree. Thus far it is not known what makes affine-invariant properties locally testable - no characterizations are known, and till this work it was not clear if they satisfied any closure properties. This work shows that the class of locally testable affine-invariant properties are closed under some very natural operations. Our techniques use ones previously developed for the study of \"single-orbit characterized\" properties, but manage to apply them to the potentially more general class of all locally testable ones via a simple connection that may be of broad interest in the study of affine-invariant properties.","abstract_html":"We prove that the class of locally testable affine-invariant properties is closed under sums, intersections and "lifts". The sum and intersection are two natural operations on linear spaces of functions, where the sum of two properties is simply their sum as a vector space. The "lift" is a less well-studied property, which creates some interesting affine-invariant properties over large domains, from properties over smaller domains. Previously such results were known for "single-orbit characterized" affine-invariant properties, which are known to be a subclass of locally testable ones, and are potentially a strict subclass. The fact that the intersection of locally-testable affine-invariant properties are locally testable could have been derived from previously known general results on closure of property testing under set-theoretic operations, but was not explicitly observed before. The closure under sum and lifts is implied by an affirmative answer to a central question attempting to characterize locally testable affine-invariant properties, but the status of that question remains wide open. Affine-invariant properties are clean abstractions of commonly studied, and extensively used, algebraic properties such linearity and low-degree. Thus far it is not known what makes affine-invariant properties locally testable - no characterizations are known, and till this work it was not clear if they satisfied any closure properties. This work shows that the class of locally testable affine-invariant properties are closed under some very natural operations. Our techniques use ones previously developed for the study of "single-orbit characterized" properties, but manage to apply them to the potentially more general class of all locally testable ones via a simple connection that may be of broad interest in the study of affine-invariant properties.","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":2013,"date_issued":"2013","date_published":"2013","updated_at":"2026-07-22T22:21:51Z","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/79229","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":["2013-06-17T19:49:13Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2013-06-17T19:49:13Z"]},{"key":"dc:date.issued","label":"Date","values":["2013"]},{"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/79229"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2013.","Cataloged from PDF version of thesis.","Includes bibliographical references (p. 31-32)."]},{"key":"dc:description.abstract","label":"Abstract","values":["We prove that the class of locally testable affine-invariant properties is closed under sums, intersections and \"lifts\". The sum and intersection are two natural operations on linear spaces of functions, where the sum of two properties is simply their sum as a vector space. The \"lift\" is a less well-studied property, which creates some interesting affine-invariant properties over large domains, from properties over smaller domains. Previously such results were known for \"single-orbit characterized\" affine-invariant properties, which are known to be a subclass of locally testable ones, and are potentially a strict subclass. The fact that the intersection of locally-testable affine-invariant properties are locally testable could have been derived from previously known general results on closure of property testing under set-theoretic operations, but was not explicitly observed before. The closure under sum and lifts is implied by an affirmative answer to a central question attempting to characterize locally testable affine-invariant properties, but the status of that question remains wide open. Affine-invariant properties are clean abstractions of commonly studied, and extensively used, algebraic properties such linearity and low-degree. Thus far it is not known what makes affine-invariant properties locally testable - no characterizations are known, and till this work it was not clear if they satisfied any closure properties. This work shows that the class of locally testable affine-invariant properties are closed under some very natural operations. Our techniques use ones previously developed for the study of \"single-orbit characterized\" properties, but manage to apply them to the potentially more general class of all locally testable ones via a simple connection that may be of broad interest in the study of affine-invariant properties."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["S.M."]},{"key":"dc:title","label":"Title","values":["Some closure features of locally testable affine-invariant properties"]}]}],"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":["2013-06-17T19:49:13Z"],"dc:date.available":["2013-06-17T19:49:13Z"],"dc:date.issued":["2013"],"dc:description":["Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2013.","Cataloged from PDF version of thesis.","Includes bibliographical references (p. 31-32)."],"dc:description.abstract":["We prove that the class of locally testable affine-invariant properties is closed under sums, intersections and \"lifts\". The sum and intersection are two natural operations on linear spaces of functions, where the sum of two properties is simply their sum as a vector space. The \"lift\" is a less well-studied property, which creates some interesting affine-invariant properties over large domains, from properties over smaller domains. Previously such results were known for \"single-orbit characterized\" affine-invariant properties, which are known to be a subclass of locally testable ones, and are potentially a strict subclass. The fact that the intersection of locally-testable affine-invariant properties are locally testable could have been derived from previously known general results on closure of property testing under set-theoretic operations, but was not explicitly observed before. The closure under sum and lifts is implied by an affirmative answer to a central question attempting to characterize locally testable affine-invariant properties, but the status of that question remains wide open. Affine-invariant properties are clean abstractions of commonly studied, and extensively used, algebraic properties such linearity and low-degree. Thus far it is not known what makes affine-invariant properties locally testable - no characterizations are known, and till this work it was not clear if they satisfied any closure properties. This work shows that the class of locally testable affine-invariant properties are closed under some very natural operations. Our techniques use ones previously developed for the study of \"single-orbit characterized\" properties, but manage to apply them to the potentially more general class of all locally testable ones via a simple connection that may be of broad interest in the study of affine-invariant properties."],"dc:description.degree":["S.M."],"dc:identifier.uri":["http://hdl.handle.net/1721.1/79229"],"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":["Some closure features of locally testable affine-invariant properties"],"dc:type":["Thesis"]},"updated_at":"2026-07-22T22:21:51Z"}