Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, April 06, 2006, 12:15 pm
Duration: This information is not available in the database
Location: This information is not available in the database
Speaker: Sofya Raskhodnikova (Weizmann Institute of Science)
Imagine having to choose between a few compression schemes to compress a very long file. Before deciding on the scheme, you might want to obtain a rough estimate on how well each scheme performs on your file. We consider the question of approximating compressibility of a string with respect to a fixed compression scheme, in sublinear time.
In the talk, we will concentrate on the run-length encoding and a
version of Lempel-Ziv as our example compression schemes. We present
algorithms and lower bounds for approximating compressibility with
respect to both schemes. We show that compressibility with respect to
Lempel-Ziv is related to approximating the support size of a
distribution. This problem has been considered under different guises
in the literature. We prove a lower bound for it, at the heart of
which is a construction of two positive integer random variables, X
and Y, with very different expectations and the following condition on
the moments up to k:
E[X]/E[Y] = E[X2]/E[Y2] = ... = E[Xk]/E[Yk].
Joint work with Dana Ron, Ronitt Rubinfeld, Amir Shpilka and Adam Smith.
Automatic MiSe System Software Version 1.4803M | admin login