Random Restrictions of High Dimensional Distributions and Uniformity Testing with Subcube Conditioning
April 29, 2020 (Zoom)

Abstract

Given a distribution p supported on {-1,1}^n, we want to test whether p is uniform or ϵ-far from uniform in total variation distance. The fact that p is a high dimensional distribution is inconsequential for the sample complexity, which is well-known to be Θ(2^{n/2} / ε^2). To benefit from the high dimensional structure, we study the subcube conditional sampling model, first considered in Bhattacharyya and Chakraborty (2018), and give a nearly optimal algorithm for testing uniformity on {-1,1}n making Õ(√n / ε^2) queries. The key ingredient is a natural notion of random restriction for distributions on {-1,1}n, and an inequality describing the behavior of the mean vector after a random restriction.

Joint work with Clement Canonne, Xi Chen, Gautam Kamath and Amit Levi.