Kolmogorov Complexity and Algorithmic Randomness
DOI10.1090/SURV/220zbMATH Open1435.68015OpenAlexW2763382833MaRDI QIDQ4599290FDOQ4599290
Authors: A. Shen, V. A. Uspenskiĭ, Nikolai K. Vereshchagin 
Publication date: 28 December 2017
Published in: Mathematical Surveys and Monographs (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1090/surv/220
Recommendations
- Randomness and intractability in Kolmogorov complexity
- Kolmogorov complexity in perspective. I: Information theory and randomness
- The Kolmogorov complexity of random reals
- Kolmogorov complexity and non-determinism
- Kolmogorov Complexity: Sources, Theory and Applications
- Around Kolmogorov complexity: basic notions and results
- Kolmogorov-Loveland stochasticity and Kolmogorov complexity
- Kolmogorov-Loveland Stochasticity and Kolmogorov Complexity
- Kolmogorov complexity in randomness extraction
- Kolmogorov complexity in randomness extraction
Research exposition (monographs, survey articles) pertaining to computer science (68-02) Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Algorithmic randomness and dimension (03D32) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Descriptive complexity and finite models (68Q19) Complexity of computation (including implicit computational complexity) (03D15)
Cited In (59)
- Imprecision in martingale- and test-theoretic prequential randomness
- The point-to-set principle and the dimensions of Hamel bases
- Prediction and MDL for infinite sequences
- A duality between one-way functions and average-case symmetry of information
- Improving the space-bounded version of Muchnik's conditional complexity theorem via ``naive derandomization
- Measurable versions of the Lovász local lemma and measurable graph colorings
- Title not available (Why is that?)
- Thinking with notations: epistemic actions and epistemic activities in mathematical practice
- On the (dis)similarities between stationary imprecise and non-stationary precise uncertainty models in algorithmic randomness
- \(K\)-trivial, \(K\)-low and MLR-low sequences: a tutorial
- Descriptive complexity of computable sequences revisited
- Inequalities for entropies and dimensions
- Extraction rates of random continuous functionals
- Some games on Turing machines and power from random strings
- Kolmogorov's Last Discovery? (Kolmogorov and Algorithmic Statistics)
- Complexity and randomness
- On the complexity and dimension of continuous finite-dimensional maps
- Non-Algorithmic Theory of Randomness
- The Normalized Algorithmic Information Distance Can Not Be Approximated
- The sum \(2^{KM(x)-K(x)}\) over all prefixes \(x\) of some binary sequence can be infinite
- Randomness deficiencies
- Title not available (Why is that?)
- Continuous randomness via transformations of 2-random sequences
- Bayesian definition of random sequences with respect to conditional probabilities
- A new approach to mathematical statistics involving the number of degrees of freedom, temperature, and symplectically conjugate quantities
- Martingales in the Study of Randomness
- Busy beavers and Kolmogorov complexity
- Complexity-based permutation entropies: from deterministic time series to white noise
- Title not available (Why is that?)
- Resource-bounded Kolmogorov complexity provides an obstacle to soficness of multidimensional shifts
- Algorithmic randomness and complexity.
- A theory of incremental compression
- On algorithmic statistics for space-bounded algorithms
- Title not available (Why is that?)
- The Kučera-Gács theorem revisited by Levin
- Algorithmic Fractal Dimensions in Geometric Measure Theory
- Automatic complexity. A computable measure of irregularity
- Predictions and algorithmic statistics for infinite sequences
- Finite-state independence
- Kolmogorov complexity in perspective. I: Information theory and randomness
- Computational complexity theory. Part 10. Transl. from the Russian.
- Algorithmic search in group theory
- Randomness extraction in computability theory
- Conditional probabilities and van Lambalgen's theorem revisited
- Title not available (Why is that?)
- Algorithmic statistics: forty years later
- Proofs of conservation inequalities for Levin's notion of mutual information of 1974
- Theory of computational complexity. Part 8. Transl. from the Russian
- The Intersection of Algorithmically Random Closed Sets and Effective Dimension
- Randomness Tests: Theory and Practice
- Some properties of antistochastic strings
- Information disclosure in the framework of Kolmogorov complexity
- Individual codewords
- An introduction to Kolmogorov complexity and its applications
- An operational characterization of mutual information in algorithmic information theory
- Approximating Kolmogorov complexity
- Who asked us? How the theory of computing answers questions about analysis
- Putnam's diagonal argument and the impossibility of a universal learning machine
- Vladimir Andreevich Uspensky (27/11/1930–27/6/2018)
This page was built for publication: Kolmogorov Complexity and Algorithmic Randomness
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4599290)
