{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/54663"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/54663","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"Testing and learning Boolean functions","abstract":"Given a function f on n inputs, we consider the problem of testing whether f belongs to a concept class C, or is far from every member of C. An algorithm that achieves this goal for a particular C is called a property testing algorithm, and can be viewed as relaxation of a proper learning algorithm, which must also return an approximation to f if it is in C. We give property testing algorithms for many different classes C, with a focus on those that are fundamental to machine learning, such as halfspaces, decision trees, DNF formulas, and sparse polynomials. In almost all cases, the property testing algorithm has query complexity independent of n, better than the best possible learning algorithm.","abstract_html":"Given a function f on n inputs, we consider the problem of testing whether f belongs to a concept class C, or is far from every member of C. An algorithm that achieves this goal for a particular C is called a property testing algorithm, and can be viewed as relaxation of a proper learning algorithm, which must also return an approximation to f if it is in C. We give property testing algorithms for many different classes C, with a focus on those that are fundamental to machine learning, such as halfspaces, decision trees, DNF formulas, and sparse polynomials. In almost all cases, the property testing algorithm has query complexity independent of n, better than the best possible learning algorithm.","abstract_has_math":false,"creators":["Matulef, Kevin Michael"],"institution":"Massachusetts Institute of Technology","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Dept. of Mathematics.","school":null,"contributors":[],"advisors":["Ronitt Rubinfeld."],"committee_chairs":[],"committee_members":[],"year":2009,"date_issued":"2009","date_published":"2009","updated_at":"2026-07-22T22:21:24Z","subjects":["Mathematics."],"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/54663","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 Mathematics."]},{"key":"dc:contributor.other","label":"Dc Contributor Other","values":["Massachusetts Institute of Technology. Dept. of Mathematics."]},{"key":"dc:creator","label":"Author","values":["Matulef, Kevin Michael"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2010-04-28T17:16:48Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2010-04-28T17:16:48Z"]},{"key":"dc:date.issued","label":"Date","values":["2009"]},{"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":["Mathematics."]}]},{"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/54663"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2009.","Cataloged from PDF version of thesis.","Includes bibliographical references (p. 203-207)."]},{"key":"dc:description.abstract","label":"Abstract","values":["Given a function f on n inputs, we consider the problem of testing whether f belongs to a concept class C, or is far from every member of C. An algorithm that achieves this goal for a particular C is called a property testing algorithm, and can be viewed as relaxation of a proper learning algorithm, which must also return an approximation to f if it is in C. We give property testing algorithms for many different classes C, with a focus on those that are fundamental to machine learning, such as halfspaces, decision trees, DNF formulas, and sparse polynomials. In almost all cases, the property testing algorithm has query complexity independent of n, better than the best possible learning algorithm."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["Ph.D."]},{"key":"dc:title","label":"Title","values":["Testing and learning Boolean functions"]}]}],"canonical_facts":{"dc:contributor.advisor":["Ronitt Rubinfeld."],"dc:contributor.department":["Massachusetts Institute of Technology. Dept. of Mathematics."],"dc:contributor.other":["Massachusetts Institute of Technology. Dept. of Mathematics."],"dc:creator":["Matulef, Kevin Michael"],"dc:date.accessioned":["2010-04-28T17:16:48Z"],"dc:date.available":["2010-04-28T17:16:48Z"],"dc:date.issued":["2009"],"dc:description":["Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2009.","Cataloged from PDF version of thesis.","Includes bibliographical references (p. 203-207)."],"dc:description.abstract":["Given a function f on n inputs, we consider the problem of testing whether f belongs to a concept class C, or is far from every member of C. An algorithm that achieves this goal for a particular C is called a property testing algorithm, and can be viewed as relaxation of a proper learning algorithm, which must also return an approximation to f if it is in C. We give property testing algorithms for many different classes C, with a focus on those that are fundamental to machine learning, such as halfspaces, decision trees, DNF formulas, and sparse polynomials. In almost all cases, the property testing algorithm has query complexity independent of n, better than the best possible learning algorithm."],"dc:description.degree":["Ph.D."],"dc:identifier.uri":["http://hdl.handle.net/1721.1/54663"],"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":["Mathematics."],"dc:title":["Testing and learning Boolean functions"],"dc:type":["Thesis"]},"updated_at":"2026-07-22T22:21:24Z"}