Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > COMPRESSIBILITY:
Reports tagged with compressibility:
TR03-065 | 19th June 2003
Wee, Hoeteck

Compressibility Lower Bounds in Oracle Settings

A source is compressible if we can efficiently compute short
descriptions of strings in the support and efficiently
recover the strings from the descriptions. In this paper, we
present a technique for proving lower bounds on
compressibility in an oracle setting, which yields the
following results:

- We ... more >>>




ISSN 1433-8092 | Imprint