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

We give a nearly-optimal algorithm for testing uniformity of distributions supported on -1, 1 n , which makes O( √ n/ε 2 ) many queries to a subcube conditional sampling oracle (Bhattacharyya and Chakraborty ( 2018)). The key technical component is a natural notion of random restrictions for distributions on -1, 1 n , 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.