Testing Monotone High-Dimensional Distributions.
R. Rubinfeld and R. Servedio.
Random Structures and Algorithms, 34(1), 2009, pp. 24-44.
Preliminary version in 37th Annual Symposium on Theory of Computing (STOC), 2005, pp. 147-156.


Abstract:

A {\em monotone distribution} $P$ over a (partially) ordered domain assigns higher probability to $y$ than to $x$ if $y \geq x$ in the order. We study several natural problems concerning testing properties of monotone distributions over the $n$-dimensional Boolean cube, given access to random draws from the distribution being tested. We give a poly$(n)$-time algorithm for testing whether a monotone distribution is equivalent to or $\eps$-far (in the $L_1$ norm) from the uniform distribution. A key ingredient of the algorithm is a generalization of a known isoperimetric inequality for the Boolean cube. We also introduce a method for proving lower bounds on various problems of testing monotone distributions over the $n$-dimensional Boolean cube, based on a new decomposition technique for monotone distributions. We use this method to show that our uniformity testing algorithm is optimal up to polylog$(n)$ factors, and also to give exponential lower bounds on the complexity of several other problems, including testing whether a monotone distribution is identical to or $\eps$-far from a fixed known monotone product distribution and approximating the entropy of an unknown monotone distribution.

pdf of conference version

pdf of journal version


Back to main papers page