Abstract
Distribution property testing has generated significant interest over the past decade. Given sample access to a distribution, the problem is to decide if the distribution has a property or is far from it. The problem of testing identity of a single distribution has been studied extensively and was solved recently. However, very few results are known for the problem of testing if a distribution belongs to a class of distributions. In this work we consider the well-studied class of Poisson Binomial distributions, which are sums of $n$ independent, but not necessarily identical Bernoullis. We provide a sample near-optimal algorithm for testing whether a distribution supported on $\{0,...,n\}$ to which we have sample access is an unknown Poisson Binomial distribution, or far from all Poisson Binomial distributions. The sample complexity of our algorithm is $O(n^{1/4})$ to which we provide a matching information theoretic lower bound. Our algorithm improves quadratically over the known results. This is one of the first optimal results on testing against a class of distributions. We will discuss some recent results on testing other families of distributions.