Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR03-065 | 19th June 2003 00:00

#### Compressibility Lower Bounds in Oracle Settings

TR03-065
Authors: Wee, Hoeteck
Publication: 8th September 2003 20:01
Keywords:

Abstract:

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