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 TR15-063 | 8th May 2015 20:53

A Survey on Distribution Testing: Your Data is Big. But is it Blue?

RSS-Feed




Revision #1
Authors: Clement Canonne
Accepted on: 8th May 2015 20:53
Downloads: 604
Keywords: 


Abstract:

The field of property testing originated in work on program checking, and has evolved into an established and very active research area. In this work, we survey the developments of one of its most recent and prolific offspring, distribution testing. This subfield, at the junction of property testing and Statistics, is concerned with studying properties of probability distributions.
We cover the current status of distribution testing in several settings, starting with the traditional sampling model where the algorithms obtains independent samples from the distribution. We then discuss different recent models, in which one either grants the testing algorithms more powerful types of queries, or evaluates their performance against that of an information-theoretical optimal "adversary." In each setting, we describe the state-of-the-art for a variety of testing problems.
We hope this survey will serve as a self-contained introduction for those considering research in this field.



Changes to previous version:

Added a section about competitive testing, as well as an appendix on Fano and Le Cam's methods.


Paper:

TR15-063 | 15th April 2015 22:21

A Survey on Distribution Testing: Your Data is Big. But is it Blue?





TR15-063
Authors: Clement Canonne
Publication: 15th April 2015 22:51
Downloads: 817
Keywords: 


Abstract:

The field of property testing originated in work on program checking, and has evolved into an established and very active research area. In this work, we survey the developments of one of its most recent and prolific offspring, distribution testing. This subfield, at the junction of property testing and Statistics, is concerned with studying properties of probability distributions.
We cover the current status of distribution testing in several settings, starting with the traditional sampling model where the algorithms obtains independent samples from the distribution. We then discuss different recent models, in which one either grants the testing algorithms more powerful types of queries, or evaluates their performance against that of an information-theoretical optimal ``adversary.'' In each setting, we describe the state-of-the-art for a variety of testing problems.
We hope this survey will serve as a self-contained introduction for those considering research in this field.



ISSN 1433-8092 | Imprint