Some properties of antistochastic strings

DOI10.1007/s00224-016-9695-zzbMath1378.68099arXiv1410.0310OpenAlexW2620934696MaRDI QIDQ2411042

Alexey Milovanov

Publication date: 20 October 2017

Published in: Lecture Notes in Computer Science, Theory of Computing Systems (Search for Journal in Brave)

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

zbMATH Keywords

Kolmogorov complexityalgorithmic statisticssymmetry of informationstochastic stringstotal conditional complexity

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Related Items

Some properties of antistochastic strings ⋮ Algorithmic Statistics: Forty Years Later

Cites Work

• Unnamed Item
• Unnamed Item
• Short lists with short programs in short time
• List decoding of error-correcting codes. Winning thesis of the 2002 ACM Doctoral Dissertation Competition
• Symmetry of information and one-way functions
• On symmetry of information and polynomial time invertibility
• Some properties of antistochastic strings
• Resource bounded symmetry of information revisited
• Game Arguments in Computability Theory and Algorithmic Information Theory
• Measures of Complexity
• Kolmogorov's Structure Functions and Model Selection
• Algorithmic statistics
• Kolmogorov Complexity and Algorithmic Randomness
• On Algorithmic Strong Sufficient Statistics
• An introduction to Kolmogorov complexity and its applications