Cover Image

All Kolmogorov complexity functions are optimal, but are some more optimal?

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bauwens, Bruno, Kozachinskiy, Alexander, Shen, Alexander
Format:	Preprint
Published:	2025
Subjects:	Information Theory 68Q30 H.1.1
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Equivalence of Informations Characterizes Bregman Divergences
by: Chodrow, Philip S.
Published: (2025)

Conditional normality and finite-state dimensions revisited
by: Shen, Alexander
Published: (2024)

Bishop's (up)crossing inequality and lower semicomputable random reals revisited
by: Andreev, Mikhail, et al.
Published: (2025)

The Limits of AI Explainability: An Algorithmic Information Theory Approach
by: Rao, Shrisha
Published: (2025)

Phase-Only Zero-Forcing for Secure Wireless Communication in Multi-User Systems
by: Hong, Jordan, et al.
Published: (2025)

Adaptive Greedy Rejection Sampling
by: Flamich, Gergely, et al.
Published: (2023)

Kolmogorov complexity as a combinatorial tool
by: Shen, Alexander
Published: (2024)

Greedy Poisson Rejection Sampling
by: Flamich, Gergely
Published: (2023)

Binarized Neural Networks Converge Toward Algorithmic Simplicity: Empirical Support for the Learning-as-Compression Hypothesis
by: Sakabe, Eduardo Y., et al.
Published: (2025)

Fast Algorithms for the Computation of the Minimum Distance of a Random Linear Code
by: Hernando, Fernando, et al.
Published: (2016)

Weighing Obese Timed Languages
by: Asarin, Eugene, et al.
Published: (2025)

Computing the Bandwidth of Meager Timed Automata
by: Asarin, Eugene, et al.
Published: (2024)

Implementing Basic Arithmetic in $\mathbb{F}_p$ via $\mathbb{F}_2$, and Its Application for Computing the Hamming Distance of Linear Codes
by: Hernando, Fernando, et al.
Published: (2026)

The Extremum Stack is a Minimal Sufficient Statistic for Rate-Independent Functionals: A Kolmogorov Complexity Characterisation
by: Frydrych, Piotr
Published: (2026)

A look at the Kolmogorov complexity of finite groupoids and algebras
by: Cardó, Carles
Published: (2023)

Decidability of membership problems for flat rational subsets of $\mathrm{GL}(2,\mathbb{Q})$ and singular matrices
by: Diekert, Volker, et al.
Published: (2019)

Lagrangians, Renormalization, and Quantization in Prefix Coding
by: Kolpakov, Alexander, et al.
Published: (2025)

Finite-State Machines for Horospheres in Hyperbolic Right-Angled Coxeter Groups
by: Jillson, Noah, et al.
Published: (2024)

Practical implementation of geometric quasi-cyclic LDPC codes
by: Ball, Simeon, et al.
Published: (2024)

Product gales and Finite state dimension
by: S, Akhil
Published: (2025)

Commutative N-polyregular functions
by: Lopez, Aliaume
Published: (2024)

Input-Erasing Two-Way Finite Automata
by: Meduna, Alexander, et al.
Published: (2025)

Redundancy-as-Masking: Formalizing the Artificial Age Score (AAS) to Model Memory Aging in Generative AI
by: Kayadibi, Seyma Yaman
Published: (2025)

Generalized Samorodnitsky noisy function inequalities, with applications to error-correcting codes
by: Abawonse, Olakunle S., et al.
Published: (2025)

Deterministic Suffix-reading Automata
by: Keerthan, R, et al.
Published: (2025)

List of Results on the Černý Conjecture and Reset Thresholds for Synchronizing Automata
by: Volkov, Mikhail V.
Published: (2025)

No Constant-Cost Protocol for Point--Line Incidence
by: Göös, Mika, et al.
Published: (2026)

New Construction of Locally q-ary Sequential Recoverable Codes: Parity-check Matrix Approach
by: Baghban, Akram, et al.
Published: (2025)

Optimizing the Decoding Probability and Coverage Ratio of Composite DNA
by: Cohen, Tomer, et al.
Published: (2025)

Towards a Theory of Pragmatic Information
by: Weinberger, Edward D.
Published: (2024)

M-DAB: An Input-Distribution Optimization Algorithm for Composite DNA Storage by the Multinomial Channel
by: Kobovich, Adir, et al.
Published: (2023)

Polynomial Complementation of Nondeterministic 2-Way Finite Automata by 1-Limited Automata
by: Guillon, Bruno, et al.
Published: (2025)

Curse of Slicing: Why Sliced Mutual Information is a Deceptive Measure of Statistical Dependence
by: Semenenko, Alexander, et al.
Published: (2025)

A Novel Discrete-time Model of Information Diffusion on Social Networks Considering Users Behavior
by: Van Khanh, Tran, et al.
Published: (2025)

Multiplicative Turing Ensembles, Pareto's Law, and Creativity
by: Kolpakov, Alexander, et al.
Published: (2025)

Laws of Learning Dynamics and the Core of Learners
by: Jung, Inkee, et al.
Published: (2026)

The problem of infinite information flow
by: Bian, Zheng, et al.
Published: (2025)

Propositional dynamic logic and asynchronous cascade decompositions for regular trace languages
by: Adsul, Bharat, et al.
Published: (2024)

Classically Time-Controlled Quantum Automata: Definition and Properties
by: Díaz-Caro, Alejandro, et al.
Published: (2018)

Langevin dynamics for high-dimensional optimization: the case of multi-spiked tensor PCA
by: Arous, Gérard Ben, et al.
Published: (2024)