Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR07-135 | 26th December 2007 00:00

Testing Symmetric Properties of Distributions

RSS-Feed




TR07-135
Authors: Paul Valiant, Paul Valiant
Publication: 26th December 2007 22:52
Downloads: 3763
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint