Friday 11-12
Room room # 5510 (the otehrs weren't available
Zhenming Liu
Harvard
Testing k-Wise Independence over Streaming Data

Following on the work of Indyk and McGregor [IM08], we consider the 
problem of identifying correlations
in data streams. They consider a model where a stream of pairs $(i, j) ? 
[n]^2$ arrive, giving a joint
distribution $(X, Y)$. They find approximation algorithms for how close 
the joint distribution is to the
product of the marginal distributions under various metrics, which 
naturally corresponds to how close
$X$ and $Y$ are to being independent.
We extend their main result to higher dimensions, where a stream of $m$ 
$k$-dimensional vectors in
$[n]^k$ arrive, and we wish to approximate the $\ell_2$ distance between 
the joint distribution and the product
of the marginal distributions in a single pass. Our analysis gives a 
randomized algorithm that is a $(1±\epsilon)$
approximation (with probability $1 - ?$) that requires space logarithmic 
in $n$ and $m$ and proportional
to $3^k$.