Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR10-157 | 19th April 2011 11:15

Testing Properties of Collections of Distributions

RSS-Feed




Revision #1
Authors: Reut Levi, Dana Ron, Ronitt Rubinfeld
Accepted on: 19th April 2011 11:15
Downloads: 1504
Keywords: 


Abstract:

We propose a framework for studying property testing of collections of distributions,
where the number of distributions in the collection is a parameter of the problem.
Previous work on property testing of distributions considered
single distributions or pairs of distributions. We suggest two models that differ
in the way the algorithm is given access to samples from the distributions. In one model
the algorithm may ask for a sample from any distribution of its choice, and in the other the
choice of the distribution is random.

Our main focus is on the basic problem of distinguishing between the case that all
the distributions in the collection are the same (or very similar), and the case
that it is necessary to modify the distributions in the collection in a non-negligible
manner so as to obtain this property. We give almost tight upper and lower bounds
for this testing problem, as well as study an extension to a clusterability property.
One of our lower bounds directly implies a lower bound on testing
independence of a joint distribution, a result which was left open by previous work.


Paper:

TR10-157 | 24th October 2010 15:33

Testing Properties of Collections of Distributions





TR10-157
Authors: Reut Levi, Dana Ron, Ronitt Rubinfeld
Publication: 24th October 2010 15:58
Downloads: 2441
Keywords: 


Abstract:

We propose a framework for studying property testing of collections of distributions,
where the number of distributions in the collection is a parameter of the problem.
Previous work on property testing of distributions considered
single distributions or pairs of distributions. We suggest two models that differ
in the way the algorithm is given access to samples from the distributions. In one model
the algorithm may ask for a sample from any distribution of its choice, and in the other the
choice of the distribution is random.

Our main focus is on the basic problem of distinguishing between the case that all
the distributions in the collection are the same (or very similar), and the case
that it is necessary to modify the distributions in the collection in a non-negligible
manner so as to obtain this property. We give almost tight upper and lower bounds
for this testing problem, as well as study an extension to a clusterability property.
One of our lower bounds directly implies a lower bound on testing
independence of a joint distribution, a result which was left open by previous work.



ISSN 1433-8092 | Imprint