Uniformity Testing over Hypergrids with Subcube Conditioning

We give an algorithm for testing uniformity of distributions supported on hypergrids [ m 1 ] × · · · × [ m n ], which makes 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 Canonne et al. (SODA 2021) which has the same query complexity but works for hypercubes {±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.

Authors

• Xi Chen 0001
• Cassandra Marcussen

Keywords

No keywords are indexed for this paper.