Unconditional proof of tightness of Johnson bound
Venkatesan Guruswami, Igor E. Shparlinski · Symposium on Discrete Algorithms · 2003
This paper continues the investigation of the relation between the relative distance and the list decoding radius of a binary linear code. This line of research has been pursued recently in [2, 1]. The motivation comes in part because the Johnson bound is a classical bound in coding theory and therefore it is important to understand if it can be improved for linear codes, and also because the Johnson bound, though a purely combinatorial result, also fueled a lot of the recent work on efficient list decoding algorithms (by highlighting how many errors one could hope to list decode with polynomial-sized lists) — see [1] for a detailed discussion. As usual, we denote by Fq a finite field of q elements, and recall that an [n, k] binary linear code is a kdimensional subspace of F2 ; elements in the subspace are referred to as codewords, n is called the block length and k its dimension. Its relative distance is the largest value of δ for which every pair of codewords differ in at least δn coordinates, and the list decoding radius is the largest value of e for which every Hamming ball of radius en has at most a polynomial in n number of codewords. The list decoding radius as a function of the relative distance is denoted by the function L in [2, 1] and the Johnson bound (for binary codes) can be rephrased as the statement L(δ) ≥ J(δ) def = 12 · ( 1− √ 1− 2δ ) . Guruswami [1], building upon earlier work of [2], showed that this relation is tight and that L(δ) = J(δ) assuming a widely believed number theoretic conjecture. If one includes also non-linear codes in the discussion, then it is well-known that L(δ) = J(δ), see [3]. In this work, we prove a slightly weaker bound on L(δ) without making any number-theoretic assumption. Our result shows that L(δ) ≤ J(δ) + γ0 for a very small absolute constant γ0. The larger the value of