%0 Journal Article %1 canonne2019random %A Canonne, Clément L. %A Chen, Xi %A Kamath, Gautam %A Levi, Amit %A Waingarten, Erik %D 2019 %K bounds learning probability readings stats theory %T Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning %U http://arxiv.org/abs/1911.07357 %X We give a nearly-optimal algorithm for testing uniformity of distributions supported on $\-1,1\^n$, which makes $O (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.

@article{canonne2019random, 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.}, added-at = {2019-11-19T18:18:46.000+0100}, author = {Canonne, Clément L. and Chen, Xi and Kamath, Gautam and Levi, Amit and Waingarten, Erik}, biburl = {https://www.bibsonomy.org/bibtex/2d50f230d5d45969ce0f9a711b86c7d7a/kirk86}, description = {[1911.07357] Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning}, interhash = {e5ef0b840fce08bca697d44f69b33e03}, intrahash = {d50f230d5d45969ce0f9a711b86c7d7a}, keywords = {bounds learning probability readings stats theory}, note = {cite arxiv:1911.07357Comment: 40 pages}, timestamp = {2019-11-19T18:18:46.000+0100}, title = {Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning}, url = {http://arxiv.org/abs/1911.07357}, year = 2019 }