Prediction and dimension

DOI10.1016/j.jcss.2004.10.007zbMath1161.68490OpenAlexW2769895002MaRDI QIDQ1780452

Jack H. Lutz, Lance J. Fortnow

Publication date: 13 June 2005

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2004.10.007

zbMATH Keywords

Hausdorff dimensionInformation theoryComputational complexityShannon entropyPredictionFeasible dimensionSelf-information

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Measures of information, entropy (94A17) Information theory (general) (94A15)

Related Items (6)

UNIVERSAL CODING AND PREDICTION ON ERGODIC RANDOM POINTS ⋮ Martingale families and dimension in P ⋮ Generic density and small span theorem ⋮ Generalised entropies and asymptotic complexities of languages ⋮ Dimension, entropy rates, and compression ⋮ Pushdown dimension

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A game of prediction with expert advice
• Algorithmic approach to the prediction problem
• The complexity and effectiveness of prediction algorithms
• A tight upper bound on Kolmogorov complexity and uniformly optimal prediction
• Fractal dimension and logarithmic loss unpredictability.
• On prediction of individual sequences
• Noiseless coding of combinatorial sources, Hausdorff dimension, and Kolmogorov complexity
• Finite-state dimension
• The dimensions of individual strings and sequences
• Kolmogorov complexity and Hausdorff dimension
• Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie. (Randomness and probability. An algorithmic foundation of probability theory)
• Prediction and Entropy of Printed English
• Universal prediction of individual sequences
• How to use expert advice
• Dimension in Complexity Classes
• Universal prediction
• A New Interpretation of the von Mises' Concept of Random Sequence
• A unified approach to the definition of random sequences
• The definition of random sequences

This page was built for publication: Prediction and dimension