Uniformity Testing over Hypergrids with Subcube Conditioning
Xi Chen, Cassandra Marcussen · Society for Industrial and Applied Mathematics eBooks · 2024
We give an algorithm for testing uniformity of distributions supported on hypergrids [m1] × · · · × [mn], which makes many queries to a subcube conditional sampling oracle with m = maximi. 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.