Prediction and dimension

DOI10.1016/J.JCSS.2004.10.007zbMATH Open1161.68490OpenAlexW2769895002MaRDI QIDQ1780452FDOQ1780452

Lance Fortnow, Jack H. Lutz

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

PredictionShannon entropyHausdorff dimensionComputational complexityInformation theoryFeasible dimensionSelf-information

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• The definition of random sequences
• Prediction and Entropy of Printed English
• A unified approach to the definition of random sequences
• On prediction of individual sequences
• Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie. (Randomness and probability. An algorithmic foundation of probability theory)
• How to use expert advice
• A game of prediction with expert advice
• Universal prediction of individual sequences
• Dimension in Complexity Classes
• A tight upper bound on Kolmogorov complexity and uniformly optimal prediction
• Fractal dimension and logarithmic loss unpredictability.
• Universal prediction
• A New Interpretation of the von Mises' Concept of Random Sequence
• The complexity and effectiveness of prediction algorithms
• Algorithmic approach to the prediction problem

Cited In (7)

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

   Recommendations

• Title not available (Why is that?) 👍 👎
• Fractal dimension and logarithmic loss unpredictability. 👍 👎
• The complexity and effectiveness of prediction algorithms 👍 👎
• Effective Dimensions and Relative Frequencies 👍 👎
• On complexity of easy predictable sequences 👍 👎

This page was built for publication: Prediction and dimension

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1780452)