We study monotonicity testing of high-dimensional distributions on \-1, 1\ⁿ 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~AGPRY19). We show that the subcube query complexity is (n/²), 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\ⁿ. 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/²). 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~CCKLW21). Hence, we show that monotonicity does not help, beyond logarithmic factors, in testing uniformity of distributions with subcube conditional queries.
Chakrabarty et al. (Sat,) studied this question.