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