Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR03-065 | 19th June 2003 00:00

Compressibility Lower Bounds in Oracle Settings


Authors: Wee, Hoeteck
Publication: 8th September 2003 20:01
Downloads: 1342


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 exhibit oracles relative to which there exists
samplable sources over {0,1}^n of low pseudoentropy
(say n/2) that cannot be compressed to length less than
n-\omega(log n) by polynomial size circuits.
This matches the upper bounds in [GS91, TVZ03],
and provides an oracle separation between compressibility
and pseudoentropy, thereby partially addressing an open
problem posed in [Imp99].

- In the random oracle model, we show that there exists
incompressible functions as defined in [DLN96] where any
substantial compression of the output of the function must reveal
something about the seed.

ISSN 1433-8092 | Imprint