Robust characterizations of k‐wise independence over product spaces and related testing results123. Issue 3 (7th May 2012) - Rubinfeld, Ronitt; Xie, Ning
Abstract A discrete distribution D over Σ1 ×··· ×Σn is called (non‐uniform) k ‐wise independent if for any subset of k indices i1, …, ik and for any z1∈Σ i 1<inline-graphic xlink:href="ark:/27927/pgg2pr8dczw" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />, …, zk∈Σ i k<inline-graphic xlink:href="ark:/27927/pgg2pr8dcws" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />, PrX∼D[X i 1<inline-graphic xlink:href="ark:/27927/pgg2pr8d60v" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />···X i k<inline-graphic xlink:href="ark:/27927/pgg2pr8d8f2" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /> = z1···zk] = PrX∼D[X i 1<inline-graphic xlink:href="ark:/27927/pgg2pr8d843" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /> = z1]···PrX∼D[X i k<inline-graphic xlink:href="ark:/27927/pgg2pr8d8vp" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /> = zk]. 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, 1n. 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.© 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013