# Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioning

arXiv: https://arxiv.org/abs/2502.16355 · HTML: https://mlsanity.com/paper/2502.16355/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 58 references that are in the map.
- First posted on arXiv 22 Feb 2025.

## Builds on (most cited first, 30 of 35)

- [Optimal Testing for Properties of Distributions](https://mlsanity.com/paper/1507.05952/) (2015)
- [Learning and Testing Causal Models with Interventions](https://mlsanity.com/paper/1805.09697/) (2018)
- [Testing Ising Models](https://mlsanity.com/paper/1612.03147/) (2016)
- [Testing Bayesian Networks](https://mlsanity.com/paper/1612.03156/) (2016)
- [Testing probability distributions underlying aggregated data](https://mlsanity.com/paper/1402.3835/) (2014)
- [Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning](https://mlsanity.com/paper/1911.07357/) (2019)
- [Learning and Testing Junta Distributions with Subcube Conditioning](https://mlsanity.com/paper/2004.12496/) (2020)
- [Learning Hidden Markov Models Using Conditional Samples](https://mlsanity.com/paper/2302.14753/) (2023)
- [Square Hellinger Subadditivity for Bayesian Networks and its Applications to Identity Testing](https://mlsanity.com/paper/1612.03164/) (2016)
- [Testing Shape Restrictions of Discrete Distributions](https://mlsanity.com/paper/1507.03558/) (2015)
- [Lifting uniform learners via distributional decomposition](https://mlsanity.com/paper/2303.16208/) (2023)
- [Testing Convex Truncation](https://mlsanity.com/paper/2305.03146/) (2023)
- [Faster Algorithms for Testing under Conditional Sampling](https://mlsanity.com/paper/1504.04103/) (2015)
- [Detecting Low-Degree Truncation](https://mlsanity.com/paper/2402.08133/) (2024)
- [Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models](https://mlsanity.com/paper/1901.07361/) (2019)
- [A Chasm Between Identity and Equivalence Testing with Conditional Queries](https://mlsanity.com/paper/1411.7346/) (2014)
- [Testing Identity of Multidimensional Histograms](https://mlsanity.com/paper/1804.03636/) (2018)
- [Anaconda: A Non-Adaptive Conditional Sampling Algorithm for Distribution Testing](https://mlsanity.com/paper/1807.06168/) (2018)
- [On Distribution Testing in the Conditional Sampling Model](https://mlsanity.com/paper/2007.09895/) (2020)
- [On Testing of Samplers](https://mlsanity.com/paper/2010.12918/) (2020)
- [Complexity of High-Dimensional Identity Testing with Coordinate Conditional Sampling](https://mlsanity.com/paper/2207.09102/) (2022)
- [Towards Testing Monotonicity of Distributions Over General Posets](https://mlsanity.com/paper/1907.03182/) (2019)
- [Approximating the Distance to Monotonicity of Boolean Functions](https://mlsanity.com/paper/1911.06924/) (2019)
- [Monotone probability distributions over the Boolean cube can be learned with sublinear samples](https://mlsanity.com/paper/2002.03415/) (2020)
- [Gaussian Mean Testing Made Simple](https://mlsanity.com/paper/2210.13706/) (2022)
- [Improved Bounds for High-Dimensional Equivalence and Product Testing using Subcube Queries](https://mlsanity.com/paper/2408.02347/) (2024)
- [A o(n) monotonicity tester for Boolean functions over the hypercube](https://mlsanity.com/paper/1302.4536/) (2013)
- [Uniformity Testing over Hypergrids with Subcube Conditioning](https://mlsanity.com/paper/2302.09013/) (2023)
- [On Scalable Testing of Samplers](https://mlsanity.com/paper/2306.13958/) (2023)
- [Testing Self-Reducible Samplers](https://mlsanity.com/paper/2312.10999/) (2023)

## Built on by (most cited first, 2 of 2)

- [Total Variation Distance Estimation in Autoregressive Models](https://mlsanity.com/paper/2607.19510/) (2026)
- [Testing Distributions Against Bounded Distinguishers](https://mlsanity.com/paper/2607.15645/) (2026)

## Abstract (arXiv)

We study monotonicity testing of high-dimensional distributions on -1,1n in the model of subcube conditioning, suggested and studied by Canonne, Ron, and Servedio~citeCRS15 and Bhattacharyya and Chakraborty~citeBC18. Previous work shows that the sample complexity of monotonicity testing must be exponential in n (Rubinfeld, Vasilian~citeRV20, and Aliakbarpour, Gouleakis, Peebles, Rubinfeld, Yodpinyanee~citeAGPRY19). We show that the subcube query complexity is tildeTheta(n/varepsilon2), 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~citeKMS18 to real-valued functions on -1,1n. We also study uniformity testing of distributions that are promised to be monotone, a problem introduced by Rubinfeld, Servedio~citeRS09 , using subcube conditioning. We show that the query complexity is tildeTheta(√n/varepsilon2). 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~citeCCKLW21). Hence, we show that monotonicity does not help, beyond logarithmic factors, in testing uniformity of distributions with subcube conditional queries.