Dimension extractors and optimal decompression
From MaRDI portal
Abstract: A *dimension extractor* is an algorithm designed to increase the effective dimension -- i.e., the amount of computational randomness -- of an infinite binary sequence, in order to turn a "partially random" sequence into a "more random" sequence. Extractors are exhibited for various effective dimensions, including constructive, computable, space-bounded, time-bounded, and finite-state dimension. Using similar techniques, the Kucera-Gacs theorem is examined from the perspective of decompression, by showing that every infinite sequence S is Turing reducible to a Martin-Loef random sequence R such that the asymptotic number of bits of R needed to compute n bits of S, divided by n, is precisely the constructive dimension of S, which is shown to be the optimal ratio of query bits to computed bits achievable with Turing reductions. The extractors and decompressors that are developed lead directly to new characterizations of some effective dimensions in terms of optimal decompression by Turing reductions.
Recommendations
Cites work
- scientific article; zbMATH DE number 1820017 (Why is no real title available?)
- scientific article; zbMATH DE number 2127503 (Why is no real title available?)
- scientific article; zbMATH DE number 5354052 (Why is no real title available?)
- scientific article; zbMATH DE number 3930883 (Why is no real title available?)
- scientific article; zbMATH DE number 4091484 (Why is no real title available?)
- scientific article; zbMATH DE number 3598362 (Why is no real title available?)
- scientific article; zbMATH DE number 610968 (Why is no real title available?)
- scientific article; zbMATH DE number 1010621 (Why is no real title available?)
- scientific article; zbMATH DE number 3995648 (Why is no real title available?)
- scientific article; zbMATH DE number 3307567 (Why is no real title available?)
- scientific article; zbMATH DE number 2216397 (Why is no real title available?)
- A Kolmogorov complexity characterization of constructive Hausdorff dimension.
- A Mathematical Theory of Communication
- A Pseudorandom Oracle Characterization of ${\text{BPP}}$
- A Theory of Program Size Formally Identical to Information Theory
- A unified approach to the definition of random sequences
- Almost everywhere high nonuniform complexity
- An observation on probability versus randomness with applications to complexity classes
- Compression of individual sequences via variable-rate coding
- Computational Complexity of Probabilistic Turing Machines
- Constructive Dimension and Weak Truth-Table Degrees
- Dimension Characterizations of Complexity Classes
- Dimension in Complexity Classes
- Entropy rates and finite-state dimension
- Entropy, Hausdorff measures old and new, and limit sets of geometrically finite Kleinian groups
- Every sequence is reducible to a random one
- Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws
- Finite-state dimension
- Fractal dimension and logarithmic loss unpredictability.
- Gales suffice for constructive dimension
- Independent minimum length programs to translate between given strings
- Logical Approaches to Computational Barriers
- Mathematical Foundations of Computer Science 2005
- Noiseless coding of combinatorial sources, Hausdorff dimension, and Kolmogorov complexity
- On the construction of effectively random sets
- Process complexity and effective random tests
- Randomness and Computability: Open Questions
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- STACS 2004
- STACS 2005
- THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
- The definition of random sequences
- The dimensions of individual strings and sequences
- Two definitions of fractional dimension
Cited in
(10)- Logical Approaches to Computational Barriers
- Turing degrees of reals of positive effective packing dimension
- Extracting information is hard: a Turing degree of non-integral effective Hausdorff dimension
- Feasibility of DEIM for retrieving the initial field via dimensionality reduction
- Extractors
- Constructive dimension and Turing degrees
- The Kučera-Gács theorem revisited by Levin
- scientific article; zbMATH DE number 7706045 (Why is no real title available?)
- Randomness extraction in computability theory
- Dimension Expanders via Rank Condensers
This page was built for publication: Dimension extractors and optimal decompression
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1015378)
