General linear relations between different types of predictive complexity

DOI10.1016/S0304-3975(01)00039-1zbMath0982.68075OpenAlexW2033194803MaRDI QIDQ5958290

Yuri Kalnishkan

Publication date: 3 March 2002

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(01)00039-1

zbMATH Keywords

computational learning theorygeneralisation of Kolmogorov complexitytight inequalities

Mathematics Subject Classification ID

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

Related Items (2)

Generalised entropies and asymptotic complexities of languages ⋮ Predictive Complexity for Games with Finite Outcome Spaces

Cites Work

• A game of prediction with expert advice
• The weighted majority algorithm
• How to use expert advice
• Minimum Message Length and Kolmogorov Complexity
• Complexity Approximation Principle
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• Probability theory for the Brier game
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: General linear relations between different types of predictive complexity