Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-235 | 8th October 2026 16:48

The One-and-a-Half Johnson Bound Is Tight for Proximity Gaps of General Linear Codes

RSS-Feed




TR26-235
Authors: Scott Duke Kominers, Justin Thaler, Kai Zhe Zheng
Publication: 8th October 2026 17:50
Downloads: 41
Keywords: 


Abstract:

For a linear code $C\subseteq\mathbb{F}_q^n$, we say that $C$ satisfies the \emph{proximity-gaps property} up to distance $\delta_1$ if, for every $\delta_2>\delta_1$ and every $f,g\in\mathbb{F}_q^n$, at least one of which is $\delta_2$-far from $C$ in relative Hamming distance, there are only a small fraction (typically at most $\operatorname{poly}(n)/q$) of \emph{exceptional coefficients} $z\in\mathbb{F}_q$ for which $f+zg$ is $\delta_1$-close to $C$. Prior work shows that every linear code of relative distance $\delta$ satisfies proximity gaps up to the one-and-a-half Johnson radius $J_{3/2}(\delta)=1-(1-\delta)^{1/3}$. We prove that this threshold is tight at every distance $0<\delta<1$ for general linear codes. Specifically, for every $0<\delta<1$, we construct a linear code of relative distance arbitrarily close to $\delta$ and words $f,g$ that are both $\left(1-(1-\delta)^{4/9}\right)$-far from the code, but have a constant fraction of coefficients $z$ for which $f+zg$ is nearly $J_{3/2}(\delta)$-close to the code. Our counterexamples continue to hold even when a fixed amount of distance-dependent slack is allowed.



ISSN 1433-8092 | Imprint