Improved Distribution Testing for Shape Restrictions (Eldar Fischer)
Abstract: Distribution testing deals with the question of what information can be deduced about an unknown distribution over {1,...,n}, where we are only allowed to obtain a relatively small number of independent samples from the distribution. In the basic model, the algorithm may only base its decision on a provided sequence of independent samples from the distribution, while in the conditional model the algorithm may also request samples from the distribution when conditioned over subsets of {1,...,n}, specified in the request.
A test has to distinguish a distribution satisfying a given property from a distribution that is far in the variation distance from satisfying it. A range of properties, such as monotonicity and log-concavity, has been unified under the banner of L-decomposable properties. Here we improve upon the basic model test for all such properties, as well as provide a new test under the conditional model whose number of queries does not directly depend on n. We also provide a conditional model test for a wider range of properties, that in particular yields tolerant testing for all L-decomposable properties. For tolerant testing, access to conditional samples is essential, as there is a known near-linear lower bound without them.
Our main mechanism is a way of efficiently producing a partition of {1,...,n} into intervals, satisfying a small-weight requirement with respect to the unknown distribution. Also, we show that investigating just one such partition is sufficient for solving the testing question, as opposed to prior works where a search for the "correct" partition was performed.
Joint work with Oded Lachish and Yadu Vasudev.
