## May 29, Spring Quarter 2009: Thoery Seminar

### 1:00pm in 253 ICS

# Measuring Independence of Datasets

## Vladimir Braverman, UCLA

A data stream model represents setting where approximating pairwise,
or $k$-wise, independence with sublinear memory is of considerable importance.
In the streaming model the joint distribution is given by a stream of $k$-tuples,
with the goal of testing correlations among the components measured over the entire stream.
Indyk and McGregor (SODA 08) recently gave exciting new results for measuring
pairwise independence in the streaming model.
The Indyk and McGregor methods provide $\log{n}$-approximation under
statistical distance between the joint and product distributions in the streaming model.
Indyk and McGregor leave, as their main open question, the problem of improving their
$\log n$-approximation for the statistical distance metric.

This talk covers our recent paper "Measuring Independence of Datasets" (submitted).
We solve the main open problem posed by of Indyk and McGregor
for the statistical distance for pairwise independence and extend this
result to any constant $k$. In particular, we present an algorithm that computes
an $(\epsilon, \delta)$-approximation
of the statistical distance between the joint and product distributions
defined by a stream of $k$-tuples.
Our algorithm requires $O(\left({1\over \epsilon}\log({nm\over \delta})\right)^{(30+k)^k})$
memory and a single pass over the data stream.

Joint work with Rafail Ostrovsky (UCLA).