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