Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR19-165 | 18th November 2019 00:32

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

RSS-Feed




TR19-165
Authors: Clement Canonne, Xi Chen, Gautam Kamath, Amit Levi, Erik Waingarten
Publication: 18th November 2019 03:16
Downloads: 951
Keywords: 


Abstract:

We give a nearly-optimal algorithm for testing uniformity of distributions supported on $\{-1,1\}^n$, which makes $\tilde O (\sqrt{n}/\varepsilon^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.



ISSN 1433-8092 | Imprint