  A probability distribution over {-1, 1}^n is (eps, k)-wise uniform if,
roughly, it is eps-close to the uniform distribution when restricted to any k
coordinates. We consider the problem of how far an (eps, k)-wise uniform
distribution can be from any globally k-wise uniform distribution. We show that
every (eps, k)-wise uniform distribution is O(n^(k/2) eps)-close to a k-wise
uniform distribution in total variation distance. In addition, we show that
this bound is optimal for all even k: we find an (eps, k)-wise uniform
distribution that is Omega(n^(k/2) eps)-far from any k-wise uniform
distribution in total variation distance. For k = 1, we get a better upper
bound of O(eps), which is also optimal.
  One application of our closeness result is to the sample complexity of
testing whether a distribution is k-wise uniform or delta-far from k-wise
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. delta-far
from k-wise 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 [AAK+07], and have
simpler proofs.
