Testing non-uniform k-wise independent distributions over product spaces Conference

Rubinfeld, R, Xie, N. (2010). Testing non-uniform k-wise independent distributions over product spaces . Lecture Notes in Computer Science, 6198 LNCS(PART 1), 565-581. 10.1007/978-3-642-14165-2_48

cited authors

  • Rubinfeld, R; Xie, N

abstract

  • A distribution D over ∑1×⋯×∑ n is called (non-uniform) k-wise independent if for any set of k indices {i 1, ..., i k } and for any , . 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 the set of 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 for the binary field. 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. These greatly generalize the results of Alon et al. [1] on uniform k-wise independence over the binary field 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 when k is a constant. The main technical tools employed include discrete Fourier transforms and the theory of linear systems of congruences. © 2010 Springer-Verlag Berlin Heidelberg.

authors

publication date

  • August 12, 2010

published in

Digital Object Identifier (DOI)

start page

  • 565

end page

  • 581

volume

  • 6198 LNCS

issue

  • PART 1