Algorithmic Statistics: Forty Years Later

DOI10.1007/978-3-319-50062-1_41zbMath1365.68297arXiv1607.08077OpenAlexW2963385756WikidataQ57349370 ScholiaQ57349370MaRDI QIDQ2970987

Alexander Shen, Nikolai K. Vereshchagin

Publication date: 4 April 2017

Published in: Computability and Complexity (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1607.08077

zbMATH Keywords

probability distributionKolmogorov complexityrandomness

Mathematics Subject Classification ID

Foundations and philosophical topics in statistics (62A01) Research exposition (monographs, survey articles) pertaining to statistics (62-02) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Research exposition (monographs, survey articles) pertaining to computer science (68-02)

Related Items (10)

Randomness Tests: Theory and Practice ⋮ Inequalities for space-bounded Kolmogorov complexity ⋮ Dimension 1 sequences are close to randoms ⋮ Andrei Kolmogorov and Leonid Levin on Randomness ⋮ The Kolmogorov birthday paradox ⋮ Kolmogorov's Last Discovery? (Kolmogorov and Algorithmic Statistics) ⋮ Real patterns and indispensability ⋮ An extended coding theorem with application to quantum complexities ⋮ On algorithmic statistics for space-bounded algorithms ⋮ Predictions and algorithmic statistics for infinite sequences

Cites Work

• Unnamed Item
• Unnamed Item
• Algorithmic minimal sufficient statistics: a new approach
• Sophistication vs logical depth
• Stability of properties of Kolmogorov complexity under relativization
• Depth as randomness deficiency
• Sophistication revisited
• On the relation between descriptional complexity and algorithmic probability
• Modeling by shortest data description
• Mathematical metaphysics of randomness
• Does snooping help?
• Computational depth: Concept and applications
• Some properties of antistochastic strings
• Algorithmic tests and randomness with respect to a class of measures
• An almost machine-independent theory of program-length complexity, sophistication, and induction
• Around Kolmogorov Complexity: Basic Notions and Results
• Algorithmic Statistics Revisited
• Sophistication as Randomness Deficiency
• What Percentage of Programs Halt?
• Kolmogorov's Structure Functions and Model Selection
• Meaningful Information
• Algorithmic Minimal Sufficient Statistic Revisited
• Randomness conservation inequalities; information and independence in mathematical theories
• On the Defect of Randomness of a Finite Object with Respect to Measures with Given Complexity Bounds
• Algorithmic statistics
• Kolmogorov Complexity and Algorithmic Randomness
• Algorithmic statistics, prediction and machine learning
• Algorithmic Complexity and Stochastic Properties of Finite Binary Sequences
• Discussion on Kolmogorov Complexity and Statistical Analysis
• Approximating Rate-Distortion Graphs of Individual Data: Experiments in Lossy Compression and Denoising
• Rate Distortion and Denoising of Individual Data Using Kolmogorov Complexity
• An Information Measure for Classification
• A formal theory of inductive inference. Part I
• A formal theory of inductive inference. Part II
• Algorithmic Statistics: Normal Objects and Universal Models
• An introduction to Kolmogorov complexity and its applications

This page was built for publication: Algorithmic Statistics: Forty Years Later