loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
19th Annual IEEE Conference on Computational Complexity (CCC'04)
On Pseudoentropy versus Compressibility
Amherst, Massachusetts
June 21-June 24
ISBN: 0-7695-2120-7
ASCII Text
x 
 
Hoeteck Wee, "On Pseudoentropy versus Compressibility," Computational Complexity, Annual IEEE Conference on, pp. 29-41, 19th Annual IEEE Conference on Computational Complexity (CCC'04), 2004.
 
 
BibTex
x
 
@article{ 10.1109/CCC.2004.1313782,
author = {Hoeteck Wee},
title = {On Pseudoentropy versus Compressibility},
journal ={Computational Complexity, Annual IEEE Conference on},
volume = {0},
year = {2004},
issn = {1093-0159},
pages = {29-41},
doi = {http://doi.ieeecomputersociety.org/10.1109/CCC.2004.1313782},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Computational Complexity, Annual IEEE Conference on
TI - On Pseudoentropy versus Compressibility
SN - 1093-0159
SP29
EP41
A1 - Hoeteck Wee,
PY - 2004
KW - null
VL - 0
JA - Computational Complexity, Annual IEEE Conference on
ER -
 
Hoeteck Wee, University of California at Berkeley

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

  • 1. 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 [4, 9], and provides an oracle separation between compressibility and pseudoentropy, thereby partially addressing an open problem posed in [6].
  • 2. We also provide a separation between 1/s-metric-type pseudoentropy and 1/s-Yao-type pseudoentropy — which are two computational analogues of entropy introduced in [1] — for the class of oracle circuits of sizes (s polynomially bounded). This is the first known separation result for metric-type and Yao-type pseudoentropy.
  • 3. In the random oracle model, we show that there exists in compressible functions as defined in [3] where any substantial compression of the output of the function must reveal something about the seed. This yields the first known practical realization of incompressible functions, under the assumption that random oracles may be realized using cryptographic hash functions.

    • Finally, we show that computational assumptions are needed to separate compressibility and pseudoentropy for samplable sources. In particular, if one-way functions do not exist, then any samplable flat source of entropy k can be compressed by circuits to length k + 0(log n); furthermore, any such source has 1/2-Yao-type pseudoentropy k + 0(log n).

    Citation:
    Hoeteck Wee, "On Pseudoentropy versus Compressibility," ccc, pp.29-41, 19th Annual IEEE Conference on Computational Complexity (CCC'04), 2004
    Usage of this product signifies your acceptance of the Terms of Use.