2026-07-22T01:18:16Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9458 2024-03-06T10:44:27Z ddc:004 open_access

On Closeness to k-Wise Uniformity O'Donnell, Ryan Zhao, Yu k-wise independence property testing Fourier analysis Boolean function A probability distribution over {-1, 1}^n is (epsilon, k)-wise uniform if, roughly, it is epsilon-close 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 k-wise uniform distribution. We show that every (epsilon, k)-wise uniform distribution is O(n^{k/2}epsilon)-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 (epsilon, k)-wise uniform distribution that is Omega(n^{k/2}epsilon)-far from any k-wise 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 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 [Alon et al., 2007], and have simpler proofs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ryan O'Donnell and Yu Zhao 2018 Is Part Of LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2018.54 urn:nbn:de:0030-drops-94581 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.54 eng https://creativecommons.org/licenses/by/3.0/legalcode