Robust characterizations of k-wise independence over product spaces and related testing results Article

Rubinfeld, R, Xie, N. (2013). Robust characterizations of k-wise independence over product spaces and related testing results . 43(3), 265-312. 10.1002/rsa.20423

cited authors

  • Rubinfeld, R; Xie, N

authors

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∈Σi1,...,zk∈Σik, PrX~D[Xi1···Xik = z1···zk] = PrX~D[Xi1 = z1]···PrX~D[Xik = 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,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.© 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013 Copyright © 2012 Wiley Periodicals, Inc..

publication date

  • January 1, 2013

Digital Object Identifier (DOI)

start page

  • 265

end page

  • 312

volume

  • 43

issue

  • 3