Vladimir Braverman talk, 05/26, 1:30pm
David Kempe
Vladimir Braverman from UCLA will be giving a Theory/Database seminar talk at
USC on Tuesday, 05/26/2009, at 1:30pm. All relevant information is below. I am
looking forward to seeing many of you there.
Date: Tuesday, 05/26/2009, 1:30 pm
Location: PHE 333
[use the elevator to get to the third floor - the 3rd floor doors are locked]
Speaker: Vladimir Braverman, UCLA
Title: Measuring Independence of Datasets
Abstract:
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".
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).
Bio:
Vladimir Braverman is a PhD candidate at UCLA; his adviser is Professor Rafail
Ostrovsky. Vladimir received his bachelor and master degrees from Ben-Gurion
University, Israel. His research interests include data streams, massive data
sets and communication complexity. Before attending UCLA, Vladimir led a
research group at HyperRoll, Inc., a leading provider of data warehouse
performance acceleration software.
--
David Kempe <dke...@usc.edu>