Abstract
A probability distribution over {1, 1}^n is (epsilon, k)wise uniform if, roughly, it is epsilonclose to the uniform distribution when restricted to any k coordinates. We consider the problem of how far an (epsilon, k)wise uniform distribution can be from any globally kwise uniform distribution. We show that every (epsilon, k)wise uniform distribution is O(n^{k/2}epsilon)close to a kwise uniform distribution in total variation distance. In addition, we show that this bound is optimal for all even k: we find an (epsilon, k)wise uniform distribution that is Omega(n^{k/2}epsilon)far from any kwise uniform distribution in total variation distance. For k=1, we get a better upper bound of O(epsilon), which is also optimal.
One application of our closeness result is to the sample complexity of testing whether a distribution is kwise uniform or deltafar from kwise uniform. We give an upper bound of O(n^{k}/delta^2) (or O(log n/delta^2) when k = 1) on the required samples. We show an improved upper bound of O~(n^{k/2}/delta^2) for the special case of testing fully uniform vs. deltafar from kwise uniform. Finally, we complement this with a matching lower bound of Omega(n/delta^2) when k = 2.
Our results improve upon the best known bounds from [Alon et al., 2007], and have simpler proofs.
BibTeX  Entry
@InProceedings{odonnell_et_al:LIPIcs:2018:9458,
author = {Ryan O'Donnell and Yu Zhao},
title = {{On Closeness to kWise Uniformity}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
pages = {54:154:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770859},
ISSN = {18688969},
year = {2018},
volume = {116},
editor = {Eric Blais and Klaus Jansen and Jos{\'e} D. P. Rolim and David Steurer},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9458},
URN = {urn:nbn:de:0030drops94581},
doi = {10.4230/LIPIcs.APPROXRANDOM.2018.54},
annote = {Keywords: kwise independence, property testing, Fourier analysis, Boolean function}
}
Keywords: 

kwise independence, property testing, Fourier analysis, Boolean function 
Collection: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018) 
Issue Date: 

2018 
Date of publication: 

13.08.2018 