Speaker: Ning Xie MIT
Time: 2009-05-07 16:00-2009-05-07 17:00
Venue: FIT Building 4-603, Tsinghua University
Download: Click!

Abstract:

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.

Short Bio: