Compression and Ranking

A complexity-theoretic approach to the classical data compression problem is to define a notion of language compression by a machine in a certain complexity class, and to study language classes compressible under the above definition. Languages that can be compressed efficiently (e.g. by a probabilistic polynomial time machine) are of special interest.

Authors

• Andrew V. Goldberg
• Michael Sipser

Keywords

No keywords are indexed for this paper.