Journal
SIAM JOURNAL ON COMPUTING
Volume 40, Issue 6, Pages 1927-1968Publisher
SIAM PUBLICATIONS
DOI: 10.1137/080734066
Keywords
approximation algorithms; statistical properties; L-1 distance approximation; entropy approximation; lower bounds; Poissonization; Vandermonde matrices
Funding
- NSF [6916481]
Ask authors/readers for more resources
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 properties of one or two distributions that are symmetric and satisfy a certain weak continuity condition. Analyzing the performance of the canonical tester on specific properties resolves two 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 > 1/2 requires Omega(n(2/3)) samples.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available