Dimension, entropy rates, and compression
DOI10.1016/J.JCSS.2005.10.002zbMATH Open1103.68058OpenAlexW2031313360MaRDI QIDQ2495412FDOQ2495412
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
Recommendations
computational complexityHausdorff dimensionKolmogorov complexitycircuit complexitygatesresource-bounded dimensionscaled dimension
Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)
Cites Work
- Title not available (Why is that?)
- Finite-state dimension
- The dimensions of individual strings and sequences
- Kolmogorov complexity and Hausdorff dimension
- On Approximation Algorithms for # P
- On pseudorandomness and resource-bounded measure
- Finite state languages
- Almost everywhere high nonuniform complexity
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the entropy of context-free languages
- On counting and approximation
- A Kolmogorov complexity characterization of constructive Hausdorff dimension.
- Dimension in Complexity Classes
- Correspondence principles for effective dimensions
- Gales suffice for constructive dimension
- A tight upper bound on Kolmogorov complexity and uniformly optimal prediction
- Fractal dimension and logarithmic loss unpredictability.
- Mathematical Foundations of Computer Science 2005
- Computation times of NP sets of different densities
- Observations on measure and lowness for \(\Delta_ 2^ p\)
- P-Printable Sets
- Effective fractal dimensions
- Title not available (Why is that?)
- Compression and Ranking
- Prediction and dimension
- Scaled dimension and nonuniform complexity
- Small Spans in Scaled Dimension
- Title not available (Why is that?)
Cited In (16)
- Mathematical Foundations of Computer Science 2005
- Compression and diffusion: a joint approach to detect complexity.
- 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
- Epsilon Entropy and Data Compression
- ?-Entropy 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)
