Metraipolis › archive › dc_73dc873becbd

Maximal Kolmogorov Complexity in a Hamming Ball — arXiv:2609.11362

Source

arXiv (en)

Original

https://arxiv.org/abs/2609.11362

License (as archived)

CC0-1.0

Archived

2026-10-16T06:20:22.372Z

SHA-256 of the archived text

b0e1d3e6a12af2d02fef77b957ae9be99df574ff356814b5f52f629be4efc9fb

Stable URL of this page

https://metraipolis.com/documento/dc_73dc873becbd

How to cite

Maximal Kolmogorov Complexity in a Hamming Ball — arXiv:2609.11362 — arXiv (en), https://arxiv.org/abs/2609.11362 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_73dc873becbd (Metraipolis archive dc_73dc873becbd, sha256 b0e1d3e6a12af2d02fef77b957ae9be99df574ff356814b5f52f629be4efc9fb)

@misc{dc73dc873becbd,
  title = {Maximal Kolmogorov Complexity in a Hamming Ball — arXiv:2609.11362},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.11362},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_73dc873becbd; sha256 b0e1d3e6a12af2d02fef77b957ae9be99df574ff356814b5f52f629be4efc9fb},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.11362. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-11 in math.IT).
Categorie arXiv: Information Theory (cs.IT).
Pagina del lavoro: https://arxiv.org/abs/2609.11362 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T06:01:23.676Z dalla pagina https://arxiv.org/catchup/math.IT/2026-09-11?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).