mlsanityData to 7 Oct 2026

Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioning

arXiv 2502.16355 ↗First posted 22 Feb 2025math.ST cs.CC cs.DMcited by 2

Not on the map. Why?

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.

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

Builds on

35 of 58 references.

References · 35

  1. 2015Optimal Testing for Properties of Distributionscited by 36
  2. 2018Learning and Testing Causal Models with Interventionscited by 29
  3. 2016Testing Ising Modelscited by 23
  4. 2016Testing Bayesian Networkscited by 23
  5. 2014Testing probability distributions underlying aggregated datacited by 15
  6. 2019Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioningcited by 13
  7. 2020Learning and Testing Junta Distributions with Subcube Conditioningcited by 13
  8. 2023Learning Hidden Markov Models Using Conditional Samplescited by 12
  9. 2016Square Hellinger Subadditivity for Bayesian Networks and its Applications to Identity Testingcited by 11
  10. 2015Testing Shape Restrictions of Discrete Distributionscited by 9
  11. 2023Lifting uniform learners via distributional decompositioncited by 8
  12. 2023Testing Convex Truncationcited by 8
23 more
  1. 2015Faster Algorithms for Testing under Conditional Samplingcited by 7
  2. 2024Detecting Low-Degree Truncationcited by 7
  3. 2019Lower bounds for testing graphical models: colorings and antiferromagnetic Ising modelscited by 6
  4. 2014A Chasm Between Identity and Equivalence Testing with Conditional Queriescited by 5
  5. 2018Testing Identity of Multidimensional Histogramscited by 5
  6. 2018Anaconda: A Non-Adaptive Conditional Sampling Algorithm for Distribution Testingcited by 5
  7. 2020On Distribution Testing in the Conditional Sampling Modelcited by 4
  8. 2020On Testing of Samplerscited by 4
  9. 2022Complexity of High-Dimensional Identity Testing with Coordinate Conditional Samplingcited by 4
  10. 2019Towards Testing Monotonicity of Distributions Over General Posetscited by 3
  11. 2019Approximating the Distance to Monotonicity of Boolean Functionscited by 3
  12. 2020Monotone probability distributions over the Boolean cube can be learned with sublinear samplescited by 3
  13. 2022Gaussian Mean Testing Made Simplecited by 3
  14. 2024Improved Bounds for High-Dimensional Equivalence and Product Testing using Subcube Queriescited by 3
  15. 2013A o(n) monotonicity tester for Boolean functions over the hypercubecited by 2
  16. 2023Uniformity Testing over Hypergrids with Subcube Conditioningcited by 2
  17. 2023On Scalable Testing of Samplerscited by 2
  18. 2023Testing Self-Reducible Samplerscited by 2
  19. 2024Equivalence Testing: The Power of Bounded Adaptivitycited by 2
  20. 2024Directed Isoperimetry and Monotonicity Testing: A Dynamical Approachcited by 2
  21. 2022Directed Isoperimetric Theorems for Boolean Functions on the Hypergrid and an widetildeO(n√d) Monotonicity Testercited by 1
  22. 2023Directed Poincar'e Inequalities and L1 Monotonicity Testing of Lipschitz Functionscited by 1
  23. 2023Tight Lower Bound on Equivalence Testing in Conditional Sampling Modelcited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 2.

2 papers.

  1. 2026Total Variation Distance Estimation in Autoregressive Modelscited by 1
  2. 2026Testing Distributions Against Bounded Distinguisherscited by 0