The Kučera-Gács theorem revisited by Levin
From MaRDI portal
Publication:2682931
DOI10.1016/j.tcs.2023.113693OpenAlexW4316039531WikidataQ122394943 ScholiaQ122394943MaRDI QIDQ2682931
Alexander Shen, George Barmpalias
Publication date: 1 February 2023
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2111.00516
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Lower bounds on the redundancy in computations from random oracles via betting strategies with restricted wagers
- Kobayashi compressibility
- Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega
- Dimension extractors and optimal decompression
- Optimal redundancy in computations from random oracles
- Layerwise computability and image randomness
- Noiseless coding of combinatorial sources, Hausdorff dimension, and Kolmogorov complexity
- A Kolmogorov complexity characterization of constructive Hausdorff dimension.
- The dimensions of individual strings and sequences
- Randomness and semimeasures
- Algorithmic tests and randomness with respect to a class of measures
- Algorithmic Randomness and Complexity
- Effective Strong Dimension in Algorithmic Information and Computational Complexity
- Every sequence is reducible to a random one
- Exact Expressions for Some Randomness Tests
- Dimension in Complexity Classes
- Kolmogorov Complexity and Algorithmic Randomness
- Limits of the Kučera–Gács Coding Method
- Compression of Data Streams Down to Their Information Content
- On the construction of effectively random sets
- 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
- Logical Approaches to Computational Barriers
- An introduction to Kolmogorov complexity and its applications
This page was built for publication: The Kučera-Gács theorem revisited by Levin
