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

11/17/2019
by   Clément L. Canonne, et al.
0

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

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset