Uniformity Testing over Hypergrids with Subcube Conditioning

Abstract

We give an algorithm for testing uniformity of distributions supported on hypergrids $[m_1]\times \cdots \times [m_n]$, which makes $\tilde{O}(\text{poly}(m)\sqrt{n}/{\epsilon }^2)$ many queries to a subcube conditional sampling oracle with $m={\max }_i{m}_i$. 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 $\{\pm 1{\}}^n$ 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.

Extended results to the domain [m_1] x ... x [m_n] (previously was [m]^n); substantial revisions to the introduction and conclusion of the paper