Events — Colloquia & Seminars
Sublinear Algorithms for String Compressibility and the Distribution Support Size
Speaker: Sofya Raskhodnikova, Weizmann Institute of Science
Date: Wednesday, April 26, 2006
Talk: 12:00 PM, 366 WVH
Abstract
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[X^k]/E[Y^k].
Joint work with Dana Ron, Ronitt Rubinfeld, Amir Shpilka and Adam Smith.
Brief Biography
Sofya Raskhodnikova is a postdoctoral fellow at the Weizmann Institute of Science. She received her Ph.D. from MIT in 2003.