CS 298-2
Theory Seminar
Paul Valiant
MIT
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