Premium
Robust characterizations of k ‐wise independence over product spaces and related testing results
Author(s) -
Rubinfeld Ronitt,
Xie Ning
Publication year - 2013
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20423
Subject(s) - mathematics , characterization (materials science) , product (mathematics) , independence (probability theory) , sublinear function , combinatorics , discrete mathematics , distribution (mathematics) , upper and lower bounds , fourier transform , random variable , mathematical analysis , statistics , physics , geometry , optics
A discrete distribution D over Σ 1 ×··· ×Σ n is called (non‐uniform) k ‐wise independent if for any subset of k indices { i 1 ,…, i k } and for any z 1 ∈Σ i 1,…, z k ∈Σ i k, Pr X ∼ D [ X i 1··· X i k= z 1 ··· z k ] = Pr X ∼ D [ X i 1= z 1 ]···Pr X ∼ D [ X i k= 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.© 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013