{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/44717"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/44717","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"Testing symmetric properties of distributions","abstract":"We introduce the notion of a Canonical Tester for a class of properties on distributions, that is, a tester strong and general enough that \"a distribution property in the class is testable if and only if the Canonical Tester tests it\". We construct a Canonical Tester for the class of symmetric properties of one or two distributions, satisfying a certain weak continuity condition. Analyzing the performance of the Canonical Tester on specific properties resolves several open problems, establishing lower bounds that match known upper bounds: we show that distinguishing between entropy < a or > p on distributions over [n] requires nc/P-O(1) samples, and distinguishing whether a pair of distributions has statistical distance < a or > 0 requires n1-o(1) samples. Our techniques also resolve a conjecture about a property that our Canonical Tester does not apply to: distinguishing identical distributions from those with statistical distance > 0 requires Q(n2/3) samples.","abstract_html":"We introduce the notion of a Canonical Tester for a class of properties on distributions, that is, a tester strong and general enough that &quot;a distribution property in the class is testable if and only if the Canonical Tester tests it&quot;. We construct a Canonical Tester for the class of symmetric properties of one or two distributions, satisfying a certain weak continuity condition. Analyzing the performance of the Canonical Tester on specific properties resolves several open problems, establishing lower bounds that match known upper bounds: we show that distinguishing between entropy &lt; a or &gt; p on distributions over [n] requires nc/P-O(1) samples, and distinguishing whether a pair of distributions has statistical distance &lt; a or &gt; 0 requires n1-o(1) samples. Our techniques also resolve a conjecture about a property that our Canonical Tester does not apply to: distinguishing identical distributions from those with statistical distance &gt; 0 requires Q(n2/3) samples.","abstract_has_math":false,"creators":["Valiant, Paul (Paul Andrew)"],"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":["Silvio Micali."],"committee_chairs":[],"committee_members":[],"year":2008,"date_issued":"2008","date_published":"2008","updated_at":"2026-07-22T22:22:22Z","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/44717","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Silvio Micali."]},{"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":["Valiant, Paul (Paul Andrew)"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2009-03-16T19:33:34Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2009-03-16T19:33:34Z"]},{"key":"dc:date.issued","label":"Date","values":["2008"]},{"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/44717"]}]},{"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, 2008.","Includes bibliographical references (p. 65-66)."]},{"key":"dc:description.abstract","label":"Abstract","values":["We introduce the notion of a Canonical Tester for a class of properties on distributions, that is, a tester strong and general enough that \"a distribution property in the class is testable if and only if the Canonical Tester tests it\". We construct a Canonical Tester for the class of symmetric properties of one or two distributions, satisfying a certain weak continuity condition. Analyzing the performance of the Canonical Tester on specific properties resolves several open problems, establishing lower bounds that match known upper bounds: we show that distinguishing between entropy < a or > p on distributions over [n] requires nc/P-O(1) samples, and distinguishing whether a pair of distributions has statistical distance < a or > 0 requires n1-o(1) samples. Our techniques also resolve a conjecture about a property that our Canonical Tester does not apply to: distinguishing identical distributions from those with statistical distance > 0 requires Q(n2/3) samples."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["Ph.D."]},{"key":"dc:title","label":"Title","values":["Testing symmetric properties of distributions"]}]}],"canonical_facts":{"dc:contributor.advisor":["Silvio Micali."],"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":["Valiant, Paul (Paul Andrew)"],"dc:date.accessioned":["2009-03-16T19:33:34Z"],"dc:date.available":["2009-03-16T19:33:34Z"],"dc:date.issued":["2008"],"dc:description":["Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2008.","Includes bibliographical references (p. 65-66)."],"dc:description.abstract":["We introduce the notion of a Canonical Tester for a class of properties on distributions, that is, a tester strong and general enough that \"a distribution property in the class is testable if and only if the Canonical Tester tests it\". We construct a Canonical Tester for the class of symmetric properties of one or two distributions, satisfying a certain weak continuity condition. Analyzing the performance of the Canonical Tester on specific properties resolves several open problems, establishing lower bounds that match known upper bounds: we show that distinguishing between entropy < a or > p on distributions over [n] requires nc/P-O(1) samples, and distinguishing whether a pair of distributions has statistical distance < a or > 0 requires n1-o(1) samples. Our techniques also resolve a conjecture about a property that our Canonical Tester does not apply to: distinguishing identical distributions from those with statistical distance > 0 requires Q(n2/3) samples."],"dc:description.degree":["Ph.D."],"dc:identifier.uri":["http://hdl.handle.net/1721.1/44717"],"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":["Testing symmetric properties of distributions"],"dc:type":["Thesis"]},"updated_at":"2026-07-22T22:22:22Z"}