Asymptotic Improvements of the Gilbert-Varshamov and Minkowski Bounds for

Speaker: Professor Alex Vardy , UC San Diego


Given positive integers $n$ and $d$, let $A_2(n,d)$ denote the maximum i size i of a binary code of length $n$ and minimum distance $d$. The well-known Gilbert-Varshamov bound asserts that $A_2(n,d) \geq 2^n/V(n,d-1)$, where $V(n,d) = \sum_{i=0}^d {n \choose i}$ is the volume of a Hamming sphere of radius $d$. We show that, in fact, there exists a positive constant $c$ such that $A_2(n,d) \geq c \frac{2^n}{V(n,d-1)} \log_2 V(n,d-1)$. This exceeds the Gilbert-Varshamov bound by a factor that is linear in the length $n$. The result follows by recasting the Gilbert-Varshamov bound into a graph-theoretic framework and using the fact that the corresponding graph is locally sparse. This result has several interesting generalizations. In particular, we have recently used the same approach to improve upon the classical Minkowski bound on the density of sphere-packings in the Euclidean space $\R^n$ by a factor that is linear in $n$. Unlike previous such improvements, our proof is “constructive” in a certain well-defined sense. The new bound also gives rise to many interesting questions. For example, it is well known that random linear codes achieve the GV bound with probability approaching 1 for large $n$. Are they likely to achieve the new bound with high probability? We have recently settled this question in the negative. Thus we now have a proof that there exist binary codes that are asymptotically better than random codes. *joint work with Tao Jiang (University of Miami), Michael Krivelevich and Simon Litsyn (Tel-Aviv University)