{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/68435"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/68435","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"Testability of linear-invariant properties","abstract":"Property Testing is the study of super-efficient algorithms that solve \"approximate decision problems\" with high probability. More precisely, given a property P, a testing algorithm for P is a randomized algorithm that makes a small number of queries into its input and distinguishes between whether the input satisfies P or whether the input is \"far\" from satisfying P, where \"farness\" of an object from P is measured by the minimum fraction of places in its representation that needs to be modified in order for it to satisfy P. Property testing and ideas arising from it have had significant impact on complexity theory, pseudorandomness, coding theory, computational learning theory, and extremal combinatorics. In the history of the area, a particularly important role has been played by linearinvariant properties, i.e., properties of Boolean functions on the hypercube which are closed under linear transformations of the domain. Examples of such properties include linearity, homogeneousness, Reed-Muller codes, and Fourier sparsity. In this thesis, we describe a framework that can lead to a unified analysis of the testability of all linear-invariant properties, drawing on techniques from additive combinatorics and from graph theory. We also show the first nontrivial lowerbound for the query complexity of a natural testable linear-invariant property.","abstract_html":"Property Testing is the study of super-efficient algorithms that solve "approximate decision problems" with high probability. More precisely, given a property P, a testing algorithm for P is a randomized algorithm that makes a small number of queries into its input and distinguishes between whether the input satisfies P or whether the input is "far" from satisfying P, where "farness" of an object from P is measured by the minimum fraction of places in its representation that needs to be modified in order for it to satisfy P. Property testing and ideas arising from it have had significant impact on complexity theory, pseudorandomness, coding theory, computational learning theory, and extremal combinatorics. In the history of the area, a particularly important role has been played by linearinvariant properties, i.e., properties of Boolean functions on the hypercube which are closed under linear transformations of the domain. Examples of such properties include linearity, homogeneousness, Reed-Muller codes, and Fourier sparsity. In this thesis, we describe a framework that can lead to a unified analysis of the testability of all linear-invariant properties, drawing on techniques from additive combinatorics and from graph theory. We also show the first nontrivial lowerbound for the query complexity of a natural testable linear-invariant property.","abstract_has_math":false,"creators":["Bhattacharyya, Arnab"],"institution":"Massachusetts Institute of Technology","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science.","school":null,"contributors":[],"advisors":["Ronitt Rubinfeld."],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011","date_published":"2011","updated_at":"2026-07-22T22:21:21Z","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/68435","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Ronitt Rubinfeld."]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."]},{"key":"dc:contributor.other","label":"Dc Contributor Other","values":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."]},{"key":"dc:creator","label":"Author","values":["Bhattacharyya, Arnab"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2012-01-12T19:27:26Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2012-01-12T19:27:26Z"]},{"key":"dc:date.issued","label":"Date","values":["2011"]},{"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/68435"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2011.","Cataloged from PDF version of thesis.","Includes bibliographical references (p. 75-80)."]},{"key":"dc:description.abstract","label":"Abstract","values":["Property Testing is the study of super-efficient algorithms that solve \"approximate decision problems\" with high probability. More precisely, given a property P, a testing algorithm for P is a randomized algorithm that makes a small number of queries into its input and distinguishes between whether the input satisfies P or whether the input is \"far\" from satisfying P, where \"farness\" of an object from P is measured by the minimum fraction of places in its representation that needs to be modified in order for it to satisfy P. Property testing and ideas arising from it have had significant impact on complexity theory, pseudorandomness, coding theory, computational learning theory, and extremal combinatorics. In the history of the area, a particularly important role has been played by linearinvariant properties, i.e., properties of Boolean functions on the hypercube which are closed under linear transformations of the domain. Examples of such properties include linearity, homogeneousness, Reed-Muller codes, and Fourier sparsity. In this thesis, we describe a framework that can lead to a unified analysis of the testability of all linear-invariant properties, drawing on techniques from additive combinatorics and from graph theory. We also show the first nontrivial lowerbound for the query complexity of a natural testable linear-invariant property."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["Ph.D."]},{"key":"dc:title","label":"Title","values":["Testability of linear-invariant properties"]}]}],"canonical_facts":{"dc:contributor.advisor":["Ronitt Rubinfeld."],"dc:contributor.department":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."],"dc:contributor.other":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."],"dc:creator":["Bhattacharyya, Arnab"],"dc:date.accessioned":["2012-01-12T19:27:26Z"],"dc:date.available":["2012-01-12T19:27:26Z"],"dc:date.issued":["2011"],"dc:description":["Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2011.","Cataloged from PDF version of thesis.","Includes bibliographical references (p. 75-80)."],"dc:description.abstract":["Property Testing is the study of super-efficient algorithms that solve \"approximate decision problems\" with high probability. More precisely, given a property P, a testing algorithm for P is a randomized algorithm that makes a small number of queries into its input and distinguishes between whether the input satisfies P or whether the input is \"far\" from satisfying P, where \"farness\" of an object from P is measured by the minimum fraction of places in its representation that needs to be modified in order for it to satisfy P. Property testing and ideas arising from it have had significant impact on complexity theory, pseudorandomness, coding theory, computational learning theory, and extremal combinatorics. In the history of the area, a particularly important role has been played by linearinvariant properties, i.e., properties of Boolean functions on the hypercube which are closed under linear transformations of the domain. Examples of such properties include linearity, homogeneousness, Reed-Muller codes, and Fourier sparsity. In this thesis, we describe a framework that can lead to a unified analysis of the testability of all linear-invariant properties, drawing on techniques from additive combinatorics and from graph theory. We also show the first nontrivial lowerbound for the query complexity of a natural testable linear-invariant property."],"dc:description.degree":["Ph.D."],"dc:identifier.uri":["http://hdl.handle.net/1721.1/68435"],"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":["Testability of linear-invariant properties"],"dc:type":["Thesis"]},"updated_at":"2026-07-22T22:21:21Z"}