Testing Non-uniform $k$-wise Independent Distributions over Product Spaces

演讲人: Ning Xie MIT
时间: 2009-05-07 16:00-2009-05-07 17:00
地点:FIT Building 4-603, Tsinghua University

A distribution $D$ over $\Sigma_{1}\times \cdots \times \Sigma_{n}$ is called (non-uniform) $k$-wise independent if for any set of $k$ indices $\{i_{1}, \ldots, i_{k}\}$ and for any $\sigma_{1}\cdots \sigma_{k} \in \Sigma_{i_{1}}\times \cdots \times \Sigma_{i_{k}}$,$\Pr_{X\sim D}[X_{i_{1}}\cdots X_{i_{k}}=\sigma_{1}\cdots \sigma_{k}]=\Pr_{X\sim D}[X_{i_{1}}=\sigma_{1}]\times \cdots \times \Pr_{X\sim D}[X_{i_{k}}=\sigma_{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 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.~\cite{AAK+07} 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.

Joint work with Ronitt Rubinfeld.


Mr.Ning Xie is a Ph.D. student in MIT, and his research interest lies in complexity theory.