# Complexity of High-Dimensional Identity Testing with Coordinate Conditional Sampling

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 71 references that are in the map.
- First posted on arXiv 19 Jul 2022.

## Builds on (most cited first, 28 of 28)

- [Learning Graphical Models Using Multiplicative Weights](https://mlsanity.com/paper/1706.06274/) (2017)
- [Optimal Algorithms for Testing Closeness of Discrete Distributions](https://mlsanity.com/paper/1308.3946/) (2013)
- [Optimal Testing for Properties of Distributions](https://mlsanity.com/paper/1507.05952/) (2015)
- [Testing Ising Models](https://mlsanity.com/paper/1612.03147/) (2016)
- [Testing Bayesian Networks](https://mlsanity.com/paper/1612.03156/) (2016)
- [Optimal Testing of Discrete Distributions with High Probability](https://mlsanity.com/paper/2009.06540/) (2020)
- [Which Distribution Distances are Sublinearly Testable?](https://mlsanity.com/paper/1708.00002/) (2017)
- [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)
- [Optimal Mixing of Glauber Dynamics: Entropy Factorization via High-Dimensional Expansion](https://mlsanity.com/paper/2011.02075/) (2020)
- [Square Hellinger Subadditivity for Bayesian Networks and its Applications to Identity Testing](https://mlsanity.com/paper/1612.03164/) (2016)
- [Sampling Approximately Low-Rank Ising Models: MCMC meets Variational Methods](https://mlsanity.com/paper/2202.08907/) (2022)
- [On Mixing of Markov Chains: Coupling, Spectral Independence, and Entropy Factorization](https://mlsanity.com/paper/2103.07459/) (2021)
- [Faster Algorithms for Testing under Conditional Sampling](https://mlsanity.com/paper/1504.04103/) (2015)
- [Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models](https://mlsanity.com/paper/1901.07361/) (2019)
- [Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model](https://mlsanity.com/paper/2001.00303/) (2020)
- [Independence Testing for Bounded Degree Bayesian Network](https://mlsanity.com/paper/2204.08690/) (2022)
- [Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction](https://mlsanity.com/paper/2004.09083/) (2020)
- [Rapid Mixing for Colorings via Spectral Independence](https://mlsanity.com/paper/2007.08058/) (2020)
- [On Distribution Testing in the Conditional Sampling Model](https://mlsanity.com/paper/2007.09895/) (2020)
- [Testing Product Distributions: A Closer Look](https://mlsanity.com/paper/2012.14632/) (2020)
- [Hardness of Identity Testing for Restricted Boltzmann Machines and Potts models](https://mlsanity.com/paper/2004.10805/) (2020)
- [Spectral Independence via Stability and Applications to Holant-Type Problems](https://mlsanity.com/paper/2106.03366/) (2021)
- [From algorithms to connectivity and back: finding a giant component in random k-SAT](https://mlsanity.com/paper/2207.02841/) (2022)
- [Rapid mixing from spectral independence beyond the Boolean domain](https://mlsanity.com/paper/2007.08091/) (2020)
- [Fast sampling of satisfying assignments from random k-SAT with applications to connectivity](https://mlsanity.com/paper/2206.15308/) (2022)
- [From Coupling to Spectral Independence and Blackbox Comparison with the Down-Up Walk](https://mlsanity.com/paper/2103.11609/) (2021)
- [Optimal Closeness Testing of Discrete Distributions Made (Complex) Simple](https://mlsanity.com/paper/2204.12640/) (2022)

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

- [Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioning](https://mlsanity.com/paper/2502.16355/) (2025)
- [Sampling and Identity-Testing Without Approximate Tensorization of Entropy](https://mlsanity.com/paper/2506.23456/) (2025)
- [On approximating the f-divergence between two Ising models](https://mlsanity.com/paper/2509.05016/) (2025)
- [Testing Distributions Against Bounded Distinguishers](https://mlsanity.com/paper/2607.15645/) (2026)

## Abstract (arXiv)

We study the identity testing problem for high-dimensional distributions. Given as input an explicit distribution μ, an varepsilon>0, and access to sampling oracle(s) for a hidden distribution π, the goal in identity testing is to distinguish whether the two distributions μ and π are identical or are at least varepsilon-far apart. When there is only access to full samples from the hidden distribution π, it is known that exponentially many samples (in the dimension) may be needed for identity testing, and hence previous works have studied identity testing with additional access to various "conditional" sampling oracles. We consider a significantly weaker conditional sampling oracle, which we call the mathsfCoordinate Oracle, and provide a computational and statistical characterization of the identity testing problem in this new model. We prove that if an analytic property known as approximate tensorization of entropy holds for an n-dimensional visible distribution μ, then there is an efficient identity testing algorithm for any hidden distribution π using tildeO(n/varepsilon) queries to the mathsfCoordinate Oracle. Approximate tensorization of entropy is a pertinent condition as recent works have established it for a large class of high-dimensional distributions. We also prove a computational phase transition: for a well-studied class of n-dimensional distributions, specifically sparse antiferromagnetic Ising models over +1,-1n, we show that in the regime where approximate tensorization of entropy fails, there is no efficient identity testing algorithm unless mathsfRP=mathsfNP. We complement our results with a matching Omega(n/varepsilon) statistical lower bound for the sample complexity of identity testing in the mathsfCoordinate Oracle model.