Dimension extractors and optimal decompression
From MaRDI portal
Publication:1015378
DOI10.1007/S00224-007-9024-7zbMATH Open1166.68019arXivcs/0606078OpenAlexW1582838361MaRDI QIDQ1015378FDOQ1015378
Publication date: 8 May 2009
Published in: Theory of Computing Systems (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/cs/0606078
Recommendations
Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Applications of computability and recursion theory (03D80)
Cites Work
- A Mathematical Theory of Communication
- Title not available (Why is that?)
- Entropy, Hausdorff measures old and new, and limit sets of geometrically finite Kleinian groups
- Two definitions of fractional dimension
- Title not available (Why is that?)
- Noiseless coding of combinatorial sources, Hausdorff dimension, and Kolmogorov complexity
- Finite-state dimension
- The dimensions of individual strings and sequences
- Process complexity and effective random tests
- A Theory of Program Size Formally Identical to Information Theory
- Compression of individual sequences via variable-rate coding
- 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
- Entropy rates and finite-state dimension
- Title not available (Why is that?)
- A unified approach to the definition of random sequences
- Computational Complexity of Probabilistic Turing Machines
- Almost everywhere high nonuniform complexity
- Title not available (Why is that?)
- Title not available (Why is that?)
- Every sequence is reducible to a random one
- On the construction of effectively random sets
- Logical Approaches to Computational Barriers
- Title not available (Why is that?)
- Randomness and Computability: Open Questions
- Title not available (Why is that?)
- Title not available (Why is that?)
- A Kolmogorov complexity characterization of constructive Hausdorff dimension.
- Dimension in Complexity Classes
- Gales suffice for constructive dimension
- Fractal dimension and logarithmic loss unpredictability.
- Mathematical Foundations of Computer Science 2005
- Title not available (Why is that?)
- Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws
- Title not available (Why is that?)
- STACS 2004
- Independent minimum length programs to translate between given strings
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- Title not available (Why is that?)
- Dimension Characterizations of Complexity Classes
- An observation on probability versus randomness with applications to complexity classes
- Constructive Dimension and Weak Truth-Table Degrees
- STACS 2005
- A Pseudorandom Oracle Characterization of ${\text{BPP}}$
Cited In (10)
- Extractors
- Feasibility of DEIM for retrieving the initial field via dimensionality reduction
- Dimension Expanders via Rank Condensers
- The Kučera-Gács theorem revisited by Levin
- Constructive dimension and Turing degrees
- Turing degrees of reals of positive effective packing dimension
- Two sources are better than one for increasing the Kolmogorov complexity of infinite sequences
- Title not available (Why is that?)
- Randomness extraction in computability theory
- Logical Approaches to Computational Barriers
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)
