# Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Nov 2019.

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

- [Optimal Inference Schedules for Masked Diffusion Models](https://mlsanity.com/paper/2511.04647/) (2025)
- [Lifting uniform learners via distributional decomposition](https://mlsanity.com/paper/2303.16208/) (2023)
- [On the Computational Landscape of Replicable Learning](https://mlsanity.com/paper/2405.15599/) (2024)
- [Perfect Sampling from Pairwise Comparisons](https://mlsanity.com/paper/2211.12868/) (2022)
- [Complexity of High-Dimensional Identity Testing with Coordinate Conditional Sampling](https://mlsanity.com/paper/2207.09102/) (2022)
- [Gaussian Mean Testing Made Simple](https://mlsanity.com/paper/2210.13706/) (2022)
- [A Distributional-Lifting Theorem for PAC Learning](https://mlsanity.com/paper/2506.16651/) (2025)
- [Uniformity Testing over Hypergrids with Subcube Conditioning](https://mlsanity.com/paper/2302.09013/) (2023)
- [Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioning](https://mlsanity.com/paper/2502.16355/) (2025)
- [Total Variation Distance Estimation in Autoregressive Models](https://mlsanity.com/paper/2607.19510/) (2026)
- [Sampling and Identity-Testing Without Approximate Tensorization of Entropy](https://mlsanity.com/paper/2506.23456/) (2025)
- [Testing Credibility of Public and Private Surveys through the Lens of Regression](https://mlsanity.com/paper/2410.05458/) (2024)
- [Testing Distributions Against Bounded Distinguishers](https://mlsanity.com/paper/2607.15645/) (2026)
- [Counterfactual Probing for Parallel Unmasking with Hidden Forest Structure](https://mlsanity.com/paper/2609.37841/) (2026)

## Abstract (arXiv)

We give a nearly-optimal algorithm for testing uniformity of distributions supported on -1,1n, which makes tilde O (√n/varepsilon2) queries to a subcube conditional sampling oracle (Bhattacharyya and Chakraborty (2018)). The key technical component is a natural notion of random restriction for distributions on -1,1n, and a quantitative analysis of how such a restriction affects the mean vector of the distribution. Along the way, we consider the problem of mean testing with independent samples and provide a nearly-optimal algorithm.