Maximal Kolmogorov Complexity in a Hamming Ball
Abstract
The minimal Kolmogorov complexity of a string within Hamming distance r of a given string x is the algorithmic rate-distortion function of x, and Vereshchagin and Vitanyi characterized completely which shapes it can have. This paper is about the opposite extreme. For a binary string x of length n let g_x(r) denote the maximal Kolmogorov complexity of a string within Hamming distance r of x; we study which values, and more generally which functions of r, this quantity can attain. First we characterize, up to an additive error O(log n), the possible values of the triple (C(x),r,g_x(r)): writing r_k for the radius of a Hamming ball of cardinality about 2^k, a triple (k,r,l) is realizable if and only if log V(r_k + r) < l < min{n, k+log V(r)}, where V(a) is the cardinality of a ball of radius a. In particular, for r_k+r > n/2 both bounds collapse to n and only l = n is realizable. The two ends of this interval correspond to the two extreme ways of placing a set of complexity k in the cube: a single Hamming ball, where the lower bound comes from Harper's isoperimetric inequality, and an error-correcting code, which for the intermediate parameters we relax to a family of centers with bounded covering multiplicity, in the spirit of list decoding. Then we turn to the function r -> g_x(r) as a whole: we establish four properties that it always has, and show that the minimal and the maximal functions consistent with these properties are both attained, for every complexity level k. Which intermediate profiles are attainable remains open.
Related
- Quantitative finiteness for maximal complex totally geodesic submanifolds of non-arithmetic ball quotients
- Dimension-free estimates for the full discrete Euclidean ball maximal function
- Bounds on the Semidefinite Programming Complexity of the Euclidean Ball
- The Value of a Prompt: An LLM-Relative Kolmogorov-Complexity Approach
- Abelian maximal pattern complexity of two-dimensional words
BibTeX
@misc{kozachinskiy2026maximal,
title = {{Maximal Kolmogorov Complexity in a Hamming Ball}},
author = {Alexander Kozachinskiy and Nikolay Vereshchagin},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.11362},
eprint = {2609.11362},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.11362},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Maximal Kolmogorov Complexity in a Hamming Ball
AU - Alexander Kozachinskiy
AU - Nikolay Vereshchagin
PY - 2026
DA - 2026/09/10
PB - arXiv
DO - 10.48550/arxiv.2609.11362
UR - https://arxiv.org/abs/2609.11362
AB - The minimal Kolmogorov complexity of a string within Hamming distance r of a given string x is the algorithmic rate-distortion function of x, and Vereshchagin and Vitanyi characterized completely which shapes it can have. This paper is about the opposite extreme. For a binary string x of length n let g_x(r) denote the maximal Kolmogorov complexity of a string within Hamming distance r of x; we study which values, and more generally which functions of r, this quantity can attain. First we characterize, up to an additive error O(log n), the possible values of the triple (C(x),r,g_x(r)): writing r_k for the radius of a Hamming ball of cardinality about 2^k, a triple (k,r,l) is realizable if and only if log V(r_k + r) < l < min{n, k+log V(r)}, where V(a) is the cardinality of a ball of radius a. In particular, for r_k+r > n/2 both bounds collapse to n and only l = n is realizable. The two ends of this interval correspond to the two extreme ways of placing a set of complexity k in the cube: a single Hamming ball, where the lower bound comes from Harper's isoperimetric inequality, and an error-correcting code, which for the intermediate parameters we relax to a family of centers with bounded covering multiplicity, in the spirit of list decoding. Then we turn to the function r -> g_x(r) as a whole: we establish four properties that it always has, and show that the minimal and the maximal functions consistent with these properties are both attained, for every complexity level k. Which intermediate profiles are attainable remains open.
ER -