CS Paper Radar

Maximal Kolmogorov Complexity in a Hamming Ball

Alexander Kozachinskiy, Nikolay Vereshchagin

cs.IT ·submitted 2026-09-10 10:50 UTC · v1
theory

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Time- and Space-Efficient List Decoding up to Capacity

cs.IT cs.CC ·2026-08-16 ·Dorsa Fathollahi, Noga Ron-Zewi, Mary Wootters
similarity 0.67
Abstract

In the theory of error correcting codes, list-decoding refers to the following problem. Given a code $C \subseteq Σ^N$ and a received word $y \in Σ^N$, find all codewords $c \in C$ so that $δ(c,y) \leq ρ$, where $δ$ is relative Hamming distance and $ρ\in (0,1)$. Codes that approach the optimal trade-off between the rate $R := \log_{|Σ|}(|C|) / N$ and the list-decoding radius $ρ$ are said to achieve capacity.By now, there are constructions of capacity-achieving list-decodable codes with fast near-linear-time list-decoding algorithms, but most existing work has not considered space complexity. In a recent line of work, Cook and Moshkovitz (2024, 2025, 2026) initiated the study of low-space deterministic algorithms for error correcting codes. In particular, in their 2026 paper, they gave a construction of list-decodable codes with deterministic near-linear-time and sublinear space list-decoding algorithms. However, these codes were far from achieving capacity. In this paper, we present list-decodable codes approaching capacity with deterministic time- and space-efficient list-decoding algorithms. More precisely, for any $R \in (0,1)$ and any arbitrarily small constant $τ> 0$, we present a family of codes $C\subseteq Σ^N$ with rate $R$ that are deterministically list-decodable up to radius $ρ= 1 - R - τ$, in time $N^{1 + τ}$ and space $N^τ$ with constant output list size and constant alphabet size. Our results can be extended to capacity-achieving list-recoverable codes.

0.04

NP-Hardness of Bounded Distance Decoding for Reed-Solomon Codes

cs.CC ·2026-09-24 ·Daqing Wan, Jun Zhang
theory similarity 0.65
Abstract · 31 pages

For an $[n,K]$ Reed--Solomon code, the covering radius is $n-K$. Gandikota, Ghazi, and Grigorescu proved deterministic NP-hardness of bounded-distance decoding when the decoding radius is $d$ below the covering radius for every $1\le d\le c\log n/\log\log n$, where $c>0$ is an absolute constant. We prove that, for every fixed rational $0<α<1/2$, bounded-distance decoding is NP-complete under deterministic polynomial-time many-one reductions over explicitly represented finite extension fields for the additive gap $d=\lfloor n^α\rfloor$ below the covering radius. The hard codes have odd block length~$n$, dimension $K=(n+1)/2-d$, decoding radius $(n-1)/2$, and rate tending to $1/2$. The alphabet size is subexponential in the evaluation set size: for a fixed $0<η<1$ depending only on $α$, it is $2^{Θ(n^η\log n)}=2^{o(n)}$. The proof passes through moments subset sum on $n-1$ nonzero field elements, with required subset size $(n-1)/2$ and $d$ prescribed moments. The arithmetic ingredient is a uniform positive-completion theorem over prime fields $\mathbb{F}_q$ with $q\ge d^{2+ρ}$, for any fixed $ρ>0$. A sharper form follows from a higher-dimensional point-count estimate based on Deligne's theorem; the weaker form used in our reduction is proved more elementarily using additive-character orthogonality, the one-variable Weil bound, a moment identity of order $2d$, and Newton identities. A universal completion pool, an extension-field quotient construction, and a deterministic linear-size simultaneous power condenser complete the reduction.

0.10

Quantitative Tiling Stability From Quadratic Discrepancy In Hamming Spaces

cs.IT math.CO ·2026-08-26 ·Valery, Grishin, Aryeh Lev Zabokritskiy
theory similarity 0.63
Abstract · 39 pages; no figures. Revised exposition and reference locators. Exact-arithmetic verification companion: https://doi.org/10.5281/zenodo.221…

Quadratic ball discrepancy measures how uniformly a code meets Hamming balls over all centers and radii. Perfect codes minimize this quantity among codes of the same cardinality. We prove a quantitative refinement: at the parameters of every perfect code other than a one-word code or the full space, the discrepancy excess over the minimum is at least an explicit positive multiple of the discrepancy at the packing radius. The latter equals the tiling defect divided by the square of the code cardinality. This defect is the total squared deviation of the covering multiplicity from one. The comparison applies to all codes of that cardinality. For one-error perfect codes, the coefficient is at least one, and no larger constant holds for all such codes; explicit coefficients depending on the parameters can be much larger. The tiling defect also measures the failure of uniform ball noise to smooth a code distribution. Consequently, the same discrepancy excess gives explicit bounds on holes, overlaps, and divergence from the uniform distribution.

0.52

Hamming and Johnson-Type Bounds for Joint Error Correction and Detection

cs.IT ·2026-11-13 ·Yulin Chen, Raymond W. Yeung
similarity 0.63
Abstract · This manuscript is a preliminary draft and is currently being revised. The final version will be posted once the revisions are complete. Com…

We derive upper bounds on the size of codes for joint error correction and detection over classical $q$-ary Hamming spaces. A $(c,c')$ joint error correcting and detecting code corrects every error of weight at most $c$ and detects every error whose weight lies between $c+1$ and $c+c'$. We establish equivalent conditions for this decoding requirement using Hamming balls and Hamming rings, and derive a joint bound that reduces to the Hamming bound when $c'=0$. We introduce joint perfect codes and show that binary repetition codes attain the joint bound whenever $n=2c+c'+1$. For codes satisfying $d_{\min}=2c+c'+1$, we investigate an alternative joint bound based on ring multiplicity and constant-weight code bounds. A further argument using the Cauchy-Schwarz inequality and pairwise ring intersections yields a refined joint bound that is always at least as strong as the original joint bound. We then incorporate an additional outer Hamming shell to obtain a Johnson-type extension. This extension provides a strict improvement for binary codes with $c'=1$, $d_{\min}=2c+2$, $c\geq2$, and $d_{\min}+2\leq n\leq3d_{\min}/2-1$. These results connect sphere-packing bounds with the geometry of joint error correction and detection.

0.12

Superpolynomial Lists for Reed-Solomon Codes over Binary Extension Fields

cs.IT cs.CC ·2026-10-11 ·Minshen Zhu
similarity 0.63
Abstract

Recent work shows that ordinary Reed--Solomon codes over prime fields admit polynomial-size lists up to list-decoding capacity on every evaluation set. We show a contrasting phenomenon over binary extension fields. For every fixed rate $0<R<1$, there exists $\varepsilon_R>0$ such that, for all sufficiently large $h$, the full-field Reed--Solomon code over $\mathbb{F}_{2^h}$ has a received word with $n^{Ω_R(\log n)}$ codewords within relative distance $1-R-\varepsilon_R$. To our knowledge, these are the first superpolynomial ordinary Reed--Solomon list-size lower bounds at fixed positive rate and a fixed positive agreement gap above the rate. Thus capacity-approaching polynomial list size for Reed--Solomon codes is not uniform over the underlying field, and the obstruction occurs at every fixed rate. As a puncturing consequence, the same holds for primitive Reed--Solomon codes; the obstruction is also robust under controlled dense puncturing. The proof begins with an exact correspondence that turns certain binary Bose--Chaudhuri--Hocquenghem weight-enumerator coefficients into sizes of single Reed--Solomon lists. A classical binary weight family gives the initial quarter-rate construction, while a quadratic-form enumeration supplies its superpolynomial multiplicity. A common-kernel quotient/descent argument and common-root padding then extend the construction to all rates. We also determine the optimized agreement envelope achieved by the construction.

0.36

Combinatorial limitations of list-decoding Reed-Solomon codes

cs.IT cs.CC ·2026-11-05 ·Omar Alrabiah, Rohan Goyal, Venkatesan Guruswami
similarity 0.63
Abstract · 24 pages

For infinitely many rates $R \in (0,1)$, we show that full-length Reed-Solomon codes over fields of low characteristic can contain super-polynomially many codewords in a Hamming ball of radius just exceeding the Johnson radius. Over prime fields, we exhibit full-length Reed-Solomon codes of constant rate $R$ with polynomially many codewords in a Hamming ball of relative radius bounded strictly below $1-R$. This refutes a recent conjecture that, over prime fields, list sizes below capacity are always bounded by a constant. Together, these results demonstrate that certain restrictions in recent works on explicit Reed-Solomon codes achieving list-decoding capacity, related to the choice of field or evaluation points or to the list-size guarantee, are inherent.

0.36

Average pairwise Hamming distance of a subset in a hypercube

cs.DM math.COcs.IT ·2026-10-29 ·Yijia Fang, Hao Huang
theory similarity 0.63
Abstract

In this note, we prove that for a subset $\mathcal{F}$ of $\{0,1\}^n$ of density $\frac{1}{8}$, its average pairwise Hamming distance is at least $\frac{n-3}{2}$, with equality attained only by $(n-3)$-dimensional subcubes. This answers a question of Lei Yu, and solves an important open case of a more general question posed by Ahlswede and Katona in 1977.

0.26

The half-rate linear programming bound for binary codes is $\frac12-\frac1π$

cs.IT math.CO ·2026-09-03 ·Andrew Salmon
theory similarity 0.62
Abstract · 33 pages

In their work on sphere packing and the modular bootstrap, Afkhami-Jeddi, Cohn, Hartman, de Laat, and Tajdini conjectured the exact high-dimensional exponent of the Cohn-Elkies sphere-packing linear program. OpenAI's Chapter 1 subsequently proved their conjecture by establishing that both Fourier sign-uncertainty radii are $(1/π+o(1))\sqrt d$. We prove the binary coding analogue: \[ R_D\!\left(\frac12-\frac1π\right)=\frac12. \] We also formulate the two Krawtchouk sign-uncertainty problems and determine both of their asymptotics. If $A^{\mathrm K}_{\pm}(n)$ denotes the smallest radius $r$ for which a nonzero Krawtchouk $(\pm1)$-eigenfunction $f$ exists with $f(0) = 0$ and $f(x) \ge 0$ for all $|x| \ge r$, then \[ \frac{A^{\mathrm K}_{\pm}(n)}n\longrightarrow \frac12-\frac1π. \] The lower bound proves a mass-concentration principle similar to OpenAI's Chapter 1 for Hamming space. The upper bound, on the other hand, follows the approach of the spherical-code construction in OpenAI's Chapter 2. Gay, Jeronimo, and Liu formulated a hierarchy for binary codes analogous to the spherical-code construction and improved the best known binary coding rate bounds by evaluating the first level of the corresponding hierarchy. We prove this hierarchy bounds the Delsarte program and give a construction at arbitrarily deep levels of the hierarchy, attaining the upper bound in the limit. The construction uses an $N$-qubit generalization of the pure-state channel of Alrabiah and Guruswami.

0.52