Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioning

We study monotonicity testing of high-dimensional distributions on {−1,1} n in the model of subcube conditioning, suggested and studied by Canonne, Ron, and Servedio and Bhattacharyya and Chakraborty. Previous work shows that the sample complexity of monotonicity testing must be exponential in n (Rubinfeld, Vasilian, and Aliakbarpour, Gouleakis, Peebles, Rubinfeld, Yodpinyanee). We show that the subcube query complexity is Θ( n /є 2 ), by proving nearly matching upper and lower bounds. Our work is the first to use directed isoperimetric inequalities (developed for function monotonicity testing) for analyzing a distribution testing algorithm. Along the way, we generalize an inequality of Khot, Minzer, and Safra to real-valued functions on {−1,1} n . We also study uniformity testing of distributions that are promised to be monotone, a problem introduced by Rubinfeld, Servedio, using subcube conditioning. We show that the query complexity is Θ(√ n /є 2 ). Our work proves the lower bound, which matches (up to poly-logarithmic factors) the uniformity testing upper bound for general distributions (Canonne, Chen, Kamath, Levi, Waingarten). Hence, we show that monotonicity does not help, beyond logarithmic factors, in testing uniformity of distributions with subcube conditional queries.

Authors

• Deeparnab Chakrabarty
• Xi Chen 0001
• Simeon Ristic
• C. Seshadhri 0001
• Erik Waingarten

Keywords

No keywords are indexed for this paper.