Robust characterizations of k-wise independence over product spaces and related testing results
A discrete distribution D over Sigma(1) x .... x Sigma(n) is called (non-uniform) k-wise independent if for any subset of k indices {i(1), ..., i(k)} and for any z(1) is an element of Sigma(i1), ..., z(k) is an element of Sigma(ik), Pr-X similar to D[X-i1 ... X-ik = z(1) ... z(k)] = Pr-X similar to D[X-i1 = z(1)] ... Pr-X similar to D[X-ik = z(k)]. We study the problem of testing (non-uniform) k-wise independent distributions over product spaces. For the uniform case we show an upper bound on the distance between a distribution D from k-wise independent distributions in terms of the sum of Fourier coefficients of D at vectors of weight at most k. Such a bound was previously known only when the underlying domain is {0, 1}(n). For the non-uniform case, we give a new characterization of distributions being k-wise independent and further show that such a characterization is robust based on our results for the uniform case. These results greatly generalize those of Alon et al. (STOC' 07, pp. 496-505) on uniform k-wise independence over the Boolean cubes to non-uniform k-wise independence over product spaces. Our results yield natural testing algorithms for k-wise independence with time and sample complexity sublinear in terms of the support size of the distribution when k is a constant. The main technical tools employed include discrete Fourier transform and the theory of linear systems of congruences. (C) 2012 Wiley Periodicals, Inc.
discrete distributions property testing k -wise independence fourier analysis