Dimension is compression

DOI10.1007/S00224-012-9417-0MaRDI QIDQ1946504zbMATH OpenOpenAlexWikidataFDO

Authors 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 complexityeffective dimensioninformation theory

Mathematics Subject Classification ID

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

Recommendations

• Mathematical Foundations of Computer Science 2005
• scientific article; zbMATH DE number 5269064
• Dimension, entropy rates, and compression
• scientific article; zbMATH DE number 1754653
• Lempel-Ziv Dimension for Lempel-Ziv Compression

Cites work

• scientific article; zbMATH DE number 3930883 (Why is no real title available?)
• scientific article; zbMATH DE number 107482 (Why is no real title available?)
• scientific article; zbMATH DE number 1072536 (Why is no real title available?)
• scientific article; zbMATH DE number 5269064 (Why is no real title available?)
• A Kolmogorov complexity characterization of constructive Hausdorff dimension.
• A Note on polynomial-size circuits with low resource-bounded Kolmogorov complexity
• A tight upper bound on Kolmogorov complexity and uniformly optimal prediction
• A universal algorithm for sequential data compression
• Algorithmic randomness and complexity.
• Algorithms and Computation
• Bounded pushdown dimension vs Lempel Ziv information density
• Compressibility and resource bounded measure
• Compression of individual sequences via variable-rate coding
• Dimension in Complexity Classes
• Dimension, entropy rates, and compression
• Effective Strong Dimension in Algorithmic Information and Computational Complexity
• Effective fractal dimensions
• Finite-state dimension
• Fractal dimension and logarithmic loss unpredictability.
• Kolmogorov complexity and Hausdorff dimension
• MAX3SAT is exponentially hard to approximate if NP has positive dimension.
• Noiseless coding of combinatorial sources, Hausdorff dimension, and Kolmogorov complexity
• On Hausdorff and topological dimensions of the Kolmogorov complexity of the real line
• The dimensions of individual strings and sequences

Cited in

(7)

• Mathematical Foundations of Computer Science 2005
• Structure coarsening, entropy and compressed space dimension
• Lempel-Ziv Dimension for Lempel-Ziv Compression
• Algorithmic Fractal Dimensions in Geometric Measure Theory
• On the optimal compression of sets in PSPACE
• Base invariance of feasible dimension
• Dimension, entropy rates, and compression

This page was built for publication: Dimension is compression

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