Dimension, entropy rates, and compression

DOI10.1016/J.JCSS.2005.10.002MaRDI QIDQ2495412zbMATH OpenOpenAlexFDO

Authors John M. Hitchcock, N. V. Vinodchandran

Publication date 30 June 2006

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.2005.10.002

zbMATH Keywords

computational complexityHausdorff dimensionKolmogorov complexitycircuit complexitygatesresource-bounded dimensionscaled dimension

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• Mathematical Foundations of Computer Science 2005
• Dimension is compression
• Entropy rates and finite-state dimension
• Scaled dimension and nonuniform complexity
• Dimension in Complexity Classes

Cites work

• scientific article; zbMATH DE number 3133387 (Why is no real title available?)
• scientific article; zbMATH DE number 1226899 (Why is no real title available?)
• scientific article; zbMATH DE number 1335892 (Why is no real title available?)
• scientific article; zbMATH DE number 1072536 (Why is no real title available?)
• scientific article; zbMATH DE number 2081089 (Why is no real title available?)
• A Kolmogorov complexity characterization of constructive Hausdorff dimension.
• A tight upper bound on Kolmogorov complexity and uniformly optimal prediction
• Almost everywhere high nonuniform complexity
• Compression and Ranking
• Computation times of NP sets of different densities
• Correspondence principles for effective dimensions
• Dimension in Complexity Classes
• Effective fractal dimensions
• Finite state languages
• Finite-state dimension
• Fractal dimension and logarithmic loss unpredictability.
• Gales suffice for constructive dimension
• Kolmogorov complexity and Hausdorff dimension
• Mathematical Foundations of Computer Science 2005
• Observations on measure and lowness for \(\Delta_ 2^ p\)
• On Approximation Algorithms for # P
• On counting and approximation
• On pseudorandomness and resource-bounded measure
• On the entropy of context-free languages
• P-Printable Sets
• Prediction and dimension
• Scaled dimension and nonuniform complexity
• Small Spans in Scaled Dimension
• The dimensions of individual strings and sequences

Cited in

(16)

• Compression and diffusion: a joint approach to detect complexity.
• Mathematical Foundations of Computer Science 2005
• Entropy rates and finite-state dimension
• Entropy compression versus Lovász local lemma
• A note on dimensions of polynomial size circuits
• Upward separations and weaker hypotheses in resource-bounded measure
• Rényi Information Dimension: Fundamental Limits of Almost Lossless Analog Compression
• ?-Entropy data compression
• Epsilon Entropy and Data Compression
• Scaled dimension and the Kolmogorov complexity of Turing-hard sets
• Algorithmic Fractal Dimensions in Geometric Measure Theory
• Polylog depth, highness and lowness for E
• Dimension is compression
• Base invariance of feasible dimension
• Compressibility and resource bounded measure
• Compressibility and resource bounded measure

This page was built for publication: Dimension, entropy rates, and compression

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