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)
Compression of Samplable Sources
Amherst, Massachusetts
June 21-June 24
ISBN: 0-7695-2120-7
ASCII Text
x 
 
Luca Trevisan, Salil Vadhan, David Zuckerman, "Compression of Samplable Sources," Computational Complexity, Annual IEEE Conference on, pp. 1-14, 19th Annual IEEE Conference on Computational Complexity (CCC'04), 2004.
 
 
BibTex
x
 
@article{ 10.1109/CCC.2004.1313766,
author = {Luca Trevisan and Salil Vadhan and David Zuckerman},
title = {Compression of Samplable Sources},
journal ={Computational Complexity, Annual IEEE Conference on},
volume = {0},
year = {2004},
issn = {1093-0159},
pages = {1-14},
doi = {http://doi.ieeecomputersociety.org/10.1109/CCC.2004.1313766},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Computational Complexity, Annual IEEE Conference on
TI - Compression of Samplable Sources
SN - 1093-0159
SP1
EP14
A1 - Luca Trevisan,
A1 - Salil Vadhan,
A1 - David Zuckerman,
PY - 2004
KW - null
VL - 0
JA - Computational Complexity, Annual IEEE Conference on
ER -
 
Luca Trevisan, University of California at Berkeley
Salil Vadhan, Harvard University
David Zuckerman, University of Texas
We study the compression of polynomially samplable sources. In particular, we give efficient prefix-free compression and decompression algorithms for three classes of such sources (whose support is a subset of {0, 1}^n).
  • 1. We show how to compress sources X samplable by logspace machines to expected length H(X) + O(1).
    • Our next results concern flat sources whose support is in P.
  • 2. If H(X) ≤ k = n - O(log n), we show how to compress to length k + δ ⋅ (n - k) for any constant ?δ > 0; in quasi-polynomial time we show how to compress to length k + O(polylog log(n - k)) even if k = n - polylog(n).
  • 3. If the support of X is the witness set for a self-reducible NP relation, then we show how to compress to expected length H(X) + 4.
    • Citation:
    Luca Trevisan, Salil Vadhan, David Zuckerman, "Compression of Samplable Sources," ccc, pp.1-14, 19th Annual IEEE Conference on Computational Complexity (CCC'04), 2004
    Usage of this product signifies your acceptance of the Terms of Use.