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.
展开▼
