Dimension, entropy rates, and compression

DOI10.1016/j.jcss.2005.10.002zbMath1103.68058OpenAlexW2031313360MaRDI QIDQ2495412

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

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

Related Items (7)

Dimension is compression ⋮ Base invariance of feasible dimension ⋮ Upward separations and weaker hypotheses in resource-bounded measure ⋮ A note on dimensions of polynomial size circuits ⋮ Scaled dimension and the Kolmogorov complexity of Turing-hard sets ⋮ Polylog depth, highness and lowness for E ⋮ Algorithmic Fractal Dimensions in Geometric Measure Theory

Cites Work

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

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