Maximal algorithmic complexity determined in Hamming distance neighborhoods
Maximal Kolmogorov Complexity in a Hamming Ball
Information Theory
Summary
This paper studies how complex a string can be when it's close to another string by a small number of changes. The authors look at the highest possible complexity within a set distance, unlike past work that focused on the lowest complexity. They describe exactly which complexity values can occur, using ideas from coding theory and geometry. They also identify general properties of this maximum complexity as the allowed difference grows but leave some questions open about intermediate behaviors.
What this means in practice
- •For coding engineers: Improve design limits for error-correcting codes by understanding maximal complexity distributions in neighborhood sets of codewords.
- •For compression algorithm developers: Refine algorithms that balance data compression and error tolerance by using maximal complexity profiles in data neighborhoods.
A theory result. No direct application yet.
Authors
Alexander Kozachinskiy, Nikolay Vereshchagin
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.