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.