TR07-135 Authors: Paul Valiant, Paul Valiant

Publication: 26th December 2007 22:52

Downloads: 2055

Keywords:

We 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.