Compression of Samplable Sources

Amherst, Massachusetts June 21-June 24

DOI Bookmark:

http://doi.ieeecomputersociety.org/10.1109/CCC.2004.1313766

19th Annual IEEE Conference on Comput ...

	This Article
	PURCHASE ARTICLE: $19 PDF HTML IEEE Xplore Subscribers
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Luca Trevisan Articles by Salil Vadhan Articles by David Zuckerman

	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

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.