# On closeness to k-wise uniformity

arXiv: https://arxiv.org/abs/1806.03569 · HTML: https://mlsanity.com/paper/1806.03569/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Jun 2018.

## Built on by (most cited first, 2 of 2)

- [Testing distributional assumptions of learning algorithms](https://mlsanity.com/paper/2204.07196/) (2022)
- [Logspace Reducibility From Secret Leakage Planted Clique](https://mlsanity.com/paper/2107.11886/) (2021)

## Abstract (arXiv)

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.