--------------------------------------------------------------------------
                   B O S T O N   U N I V E R S I T Y
                      Computer Science Department
                          C O L L O Q U I U M
                     Friday, December 8, 1:00 PM 
                       (Coffee served at 12:45PM)
                         Seminar Room / MCS 135
 
Piotr Indyk
MIT

Stable Distributions, Pseudorandom Generators, Embeddings and Data
Stream Computation

In recent years in Theoretical Computer Science and Databases
communities there has been a surge of interest in designing algorithms
and data structures which use *sublinear* storage (and therefore
achieve data compression). Example questions addressed are:

- Given a set $P$ of $n$ points in $d$-dimensional space, is it
  possible to represent $P$ using less than $dn$ bytes and still
  preserve (at least approximately) some important information about
  $P$, e.g., the distances between all pairs of points ?

- Is it possible to maintain such a compressed version of the data set
  dynamically ?

In this talk we show several positive results in this direction obtained
by combining the use of stable distributions with pseudorandom generators
for bounded space. In particular:

- We show how to maintain (using only $O(\log d/\epsilon^2)$ bytes) a
  sketch $C(p)$ of a point $p \in l^d_1$ under dynamic updates of its
  coordinates, such that given sketches $C(p)$ and $C(q)$ one can
  estimate $|p-q|_1$ up to a factor of $(1+\epsilon)$ with large
  probability. This solves the main open problem of the paper by
  Feigenbaum et al, FOCS'99.

- We obtain another sketch function $C'$ which maps $l^d_1$ into a
  *normed* space $l^m_1$, such that $m=m(d)$ is only polylogarithmic in
  $d$; this is the first dimensionality reduction lemma for $l_1$ norm.


Host:  George Kollios
---------------------------------------------------------------------------