Premium
Testing monotone high‐dimensional distributions
Author(s) -
Rubinfeld Ronitt,
Servedio Rocco A.
Publication year - 2009
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20247
Subject(s) - monotone polygon , mathematics , isoperimetric inequality , combinatorics , discrete mathematics , distribution (mathematics) , mathematical analysis , geometry
A monotone distribution P over a (partially) ordered domain has P ( y ) ≥ P ( x ) if y ≥ x in the order. We study several natural problems of 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 ϵ ‐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 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 (testing whether a monotone distribution is identical to or ϵ ‐far from a fixed known monotone product distribution and approximating the entropy of an unknown monotone distribution). © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009