Dimension is compression

DOI10.1007/s00224-012-9417-0zbMath1283.68175OpenAlexW2079462430WikidataQ60578949 ScholiaQ60578949MaRDI QIDQ1946504

María López-Valdés, Elvira Mayordomo

Publication date: 15 April 2013

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-012-9417-0

zbMATH Keywords

computational complexityinformation theoryeffective dimension

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Fractals (28A80) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Dynamical systems involving transformations and group actions with special properties (minimality, distality, proximality, expansivity, etc.) (37B05) Hausdorff and packing measures (28A78)

Related Items (2)

Base invariance of feasible dimension ⋮ Algorithmic Fractal Dimensions in Geometric Measure Theory

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On Hausdorff and topological dimensions of the Kolmogorov complexity of the real line
• A tight upper bound on Kolmogorov complexity and uniformly optimal prediction
• Fractal dimension and logarithmic loss unpredictability.
• Noiseless coding of combinatorial sources, Hausdorff dimension, and Kolmogorov complexity
• A Kolmogorov complexity characterization of constructive Hausdorff dimension.
• MAX3SAT is exponentially hard to approximate if NP has positive dimension.
• Finite-state dimension
• The dimensions of individual strings and sequences
• Kolmogorov complexity and Hausdorff dimension
• Dimension, entropy rates, and compression
• Compressibility and Resource Bounded Measure
• Bounded Pushdown Dimension vs Lempel Ziv Information Density
• Effective fractal dimensions
• Algorithmic Randomness and Complexity
• Effective Strong Dimension in Algorithmic Information and Computational Complexity
• A universal algorithm for sequential data compression
• Compression of individual sequences via variable-rate coding
• A Note on polynomial-size circuits with low resource-bounded Kolmogorov complexity
• Dimension in Complexity Classes
• Algorithms and Computation

This page was built for publication: Dimension is compression