Sublinear Algorithms for Approximating String Compressibility

Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld +1

We raise the question of approximating the compressibility of a string with respect to a fixed compression scheme, in sublinear time. We study this question in detail for two popul…