ECCC-Report TR07-135https://eccc.weizmann.ac.il/report/2007/135Comments and Revisions published for TR07-135en-usWed, 26 Dec 2007 22:52:15 +0200
Paper TR07-135
| Testing Symmetric Properties of Distributions |
Paul Valiant,
Paul Valiant
https://eccc.weizmann.ac.il/report/2007/135We introduce the notion of a Canonical Tester for a class of properties, that is, a tester strong and
general enough that ``a property 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 $<\alpha$ or $>\beta$ on
distributions over $[n]$ requires $n^{\alpha/\beta- o(1)}$
samples, and distinguishing whether a pair of distributions has
statistical distance $<\alpha$ or $>\beta$ 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 $>\beta$ requires $\Omega(n^{2/3})$
samples.
Wed, 26 Dec 2007 22:52:15 +0200https://eccc.weizmann.ac.il/report/2007/135