Kolmogorov Complexity and Algorithmic Randomness
From MaRDI portal
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)
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
Cited in
(75)- Vladimir Andreevich Uspensky (27/11/1930–27/6/2018)
- One-way functions and pKt complexity
- Measurable versions of the Lovász local lemma and measurable graph colorings
- 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
- scientific article; zbMATH DE number 7453171 (Why is no real title available?)
- Descriptive complexity of computable sequences revisited
- K-trivial, K-low and MLR-low sequences: a tutorial
- Imprecision in martingale- and test-theoretic prequential randomness
- Complexity and randomness
- Testing exchangeability in the batch mode with e-values and Markov alternatives
- Von Neumann entropy and quantum algorithmic randomness
- 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)
- On the complexity and dimension of continuous finite-dimensional maps
- The sum \(2^{KM(x)-K(x)}\) over all prefixes \(x\) of some binary sequence can be infinite
- Non-Algorithmic Theory of Randomness
- The Normalized Algorithmic Information Distance Can Not Be Approximated
- Randomness deficiencies
- scientific article; zbMATH DE number 7559415 (Why is no real title available?)
- A new approach to mathematical statistics involving the number of degrees of freedom, temperature, and symplectically conjugate quantities
- Quantum randomness and underdetermination
- Continuous randomness via transformations of 2-random sequences
- Bayesian definition of random sequences with respect to conditional probabilities
- Mechanical turkeys
- Busy beavers and Kolmogorov complexity
- Martingales in the Study of Randomness
- Complexity-based permutation entropies: from deterministic time series to white noise
- Resource-bounded Kolmogorov complexity provides an obstacle to soficness of multidimensional shifts
- The point-to-set principle and the dimensions of Hamel bases
- scientific article; zbMATH DE number 809134 (Why is no real title available?)
- A theory of incremental compression
- Algorithmic randomness and complexity.
- Communication complexity of the secret key agreement in algorithmic information theory
- scientific article; zbMATH DE number 1548484 (Why is no real title available?)
- The Kučera-Gács theorem revisited by Levin
- Algorithmic Fractal Dimensions in Geometric Measure Theory
- Automatic complexity. A computable measure of irregularity
- An efficient coding theorem via probabilistic representations and its applications
- Predictions and algorithmic statistics for infinite sequences
- Finite-state independence
- Statistical phase-space complexity of continuous-variable quantum channels
- Prediction and MDL for infinite sequences
- Computational complexity theory. Part 10. Transl. from the Russian.
- Kolmogorov complexity in perspective. I: Information theory and randomness
- Total conditional complexity of certain objects
- Algebraic barriers to halving algorithmic information quantities in correlated strings
- Algorithmic search in group theory
- Conditional probabilities and van Lambalgen's theorem revisited
- Finding lower bounds on the growth and entropy of subshifts over countable groups
- Randomness extraction in computability theory
- Randomness with respect to c.e. semimeasures
- scientific article; zbMATH DE number 3557669 (Why is no real title available?)
- Randomness and imprecision: from supermartingales to randomness tests
- Algorithmic statistics: forty years later
- Conditional normality and finite-state dimensions revisited
- A duality between one-way functions and average-case symmetry of information
- On the computational power of C-random strings
- Space-bounded online Kolmogorov complexity is additive
- Proofs of conservation inequalities for Levin's notion of mutual information of 1974
- Theory of computational complexity. Part 8. Transl. from the Russian
- Vladimir V'yugin: short biography and some research contributions
- Spectral approach to the communication complexity of multi-party key agreement
- The Intersection of Algorithmically Random Closed Sets and Effective Dimension
- Randomness Tests: Theory and Practice
- Individual codewords
- Information disclosure in the framework of Kolmogorov complexity
- An introduction to Kolmogorov complexity and its applications
- An operational characterization of mutual information in algorithmic information theory
- Approximating Kolmogorov complexity
- Primal logic of information
- Who asked us? How the theory of computing answers questions about analysis
- Putnam's diagonal argument and the impossibility of a universal learning machine
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)
