PostScript (120 KB)Representing Information with Computational Resource Bounds
Proceedings, 1998 Asilomar Conference on Signals, Systems, and Computers, February 1998, pp. 452-456
Abstract
A general framework for data compression, in which computational resource bounds are introduced at both the encoding and decoding end, is presented. We move away from Shannon's traditional communication system by introducing some structure in the decoder and model it by a Turing machine with finite computational resources. Information is measured using a resource bound algorithmic complexity. In this setting, we investigate the design of efficient lossy encoders.