# Uniformity Testing over Hypergrids with Subcube Conditioning

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 39 references that are in the map.
- First posted on arXiv 17 Feb 2023.

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

- [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)
- [Testing Identity of Structured Distributions](https://mlsanity.com/paper/1410.2266/) (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)
- [Downsampling for Testing and Learning in Product Distributions](https://mlsanity.com/paper/2007.07449/) (2020)
- [Testing Product Distributions: A Closer Look](https://mlsanity.com/paper/2012.14632/) (2020)
- [An optimal lower bound for monotonicity testing over hypergrids](https://mlsanity.com/paper/1304.5264/) (2013)
- [A o(d) · polylog~n Monotonicity Tester for Boolean Functions over the Hypergrid [n]d](https://mlsanity.com/paper/1710.10545/) (2017)
- [Linear Space Streaming Lower Bounds for Approximating CSPs](https://mlsanity.com/paper/2106.13078/) (2021)

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

- [Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioning](https://mlsanity.com/paper/2502.16355/) (2025)
- [Testing Distributions Against Bounded Distinguishers](https://mlsanity.com/paper/2607.15645/) (2026)

## Abstract (arXiv)

We give an algorithm for testing uniformity of distributions supported on hypergrids [m1] × cdots × [mn], which makes smashwidetildeO(poly(m)√n/ε2) many queries to a subcube conditional sampling oracle with m=maxi mi. When m is a constant, our algorithm is nearly optimal and strengthens the algorithm of [CCK+21] which has the same query complexity but works for hypercubes ± 1n only. A key technical contribution behind the analysis of our algorithm is a proof of a robust version of Pisier's inequality for functions over hypergrids using Fourier analysis.