Testing symmetric properties of distributions Export

@inproceedings{citeulike:4730006, 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 <\&\#945; or \&\#62;\&\#946; on distributions over [n] requires n \&\#945;/\&\#946;- o(1) samples, and distinguishing whether a pair of distributions has statistical distance <\&\#945; or \&\#62;\&\#946; requires n 1-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 \&\#62;\&\#946; requires \&\#937;(n 2/3 ) samples.}, address = {New York, NY, USA}, author = {Valiant, Paul}, booktitle = {STOC '08: Proceedings of the 40th annual ACM symposium on Theory of computing}, citeulike-article-id = {4730006}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1374432}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/1374376.1374432}, doi = {10.1145/1374376.1374432}, isbn = {978-1-60558-047-0}, keywords = {distributions, property\_testing, symmetry, theory}, location = {Victoria, British Columbia, Canada}, pages = {383--392}, posted-at = {2009-06-03 07:58:22}, priority = {2}, publisher = {ACM}, title = {Testing symmetric properties of distributions}, url = {http://dx.doi.org/10.1145/1374376.1374432}, year = {2008} }

TY - CONF ID - citeulike:4730006 L3 - citeulike-article-id:4730006 N2 - 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 <&#945; or &#62;&#946; on distributions over [n] requires n &#945;/&#946;- o(1) samples, and distinguishing whether a pair of distributions has statistical distance <&#945; or &#62;&#946; requires n 1-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 &#62;&#946; requires &#937;(n 2/3 ) samples. CY - Victoria, British Columbia, Canada SN - 978-1-60558-047-0 AD - New York, NY, USA EP - 392 TI - Testing symmetric properties of distributions PB - ACM T2 - STOC '08: Proceedings of the 40th annual ACM symposium on Theory of computing SP - 383 KW - distributions KW - property_testing KW - symmetry KW - theory AU - Valiant, Paul PY - 2008/// UR - http://dx.doi.org/10.1145/1374376.1374432 ER -