computational complexity

, Volume 14, Issue 3, pp 186–227

# Compression of Samplable Sources

Open AccessOriginal Paper

DOI: 10.1007/s00037-005-0198-6

Trevisan, L., Vadhan, S. & Zuckerman, D. comput. complex. (2005) 14: 186. doi:10.1007/s00037-005-0198-6

## Abstract.

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. 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.
1. 2.

If H(X) ≤ k =  n − O(log n), we show how to compress to expected length k + polylog(nk).

2. 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) + 5.

### Keywords.

Expander graphsarithmetic codingrandomized logspacepseudorandom generatorsapproximate counting

68P30

## Authors and Affiliations

1. 1.Computer Science DivisionU.C. BerkeleyBerkeleyU.S.A
2. 2.Division of Engineering and Applied SciencesHarvard UniversityCambridgeU.S.A
3. 3.Department of Computer ScienceUniversity of TexasAustinU.S.A
{"extraction_info": {"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.9574105143547058, "perplexity": 6676.995721615747}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 5, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2016-44/segments/1476988721268.95/warc/CC-MAIN-20161020183841-00020-ip-10-171-6-4.ec2.internal.warc.gz"}