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 [CRS15] and Bhattacharyya and Chakraborty [BC18] . Previous work shows that the sample complexity of monotonicity testing must be exponential in n (Rubinfeld, Vasilian [RV20], and Aliakbarpour, Gouleakis, Peebles, Rubinfeld, Yodpinyanee [AGP + 19]). 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 [KMS18] 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 [RS09], using subcube conditioning. We show that the query complexity is Θ( √ n/ε 2 ). Our work proves the lower bound, which matches (up to polylogarithmic factors) the uniformity testing upper bound for general distributions (Canonne, Chen, Kamath, Levi, Waingarten [CCK + 21]). Hence, we show that monotonicity does not help, beyond logarithmic factors, in testing uniformity of distributions with subcube conditional queries.