Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR06-080 | 16th June 2006 00:00

Dimension Extractors


Authors: David Doty
Publication: 21st June 2006 19:52
Downloads: 1260


A dimension extractor is an algorithm designed to increase the effective dimension -- i.e., the computational information density -- of an infinite sequence. A constructive dimension extractor is exhibited by showing that every sequence of positive constructive dimension is Turing equivalent to a sequence of constructive strong dimension arbitrarily close to 1. Similar results are shown for computable dimension and truth-table equivalence, and for p_ispace dimension and p_ispace Turing equivalence, where p_ispace represents Lutz's hierarchy of super-polynomial space bounds. Thus, with respect to constructive, computable, and p_ispace information density, any sequence in which almost every prefix has information density bounded away from zero can be used to compute a sequence in which infinitely many prefixes have information density that is nearly maximal. In the constructive dimension case, the reduction is uniform with respect to the input sequence: a single oracle Turing machine, taking as input a rational upper bound on the dimension of the input sequence, works for every input sequence of positive constructive dimension.

As an application, the resource-bounded extractors are used to characterize the computable dimension of individual sequences in terms of compression via truth-table reductions and to characterize the p_ispace dimension of individual sequences in terms of compression via p_ispace-bounded Turing reductions, in analogy to previous known results connecting effective dimensions to compression with effective reductions.

ISSN 1433-8092 | Imprint