Date: Tuesday, 18 Iyar 5766 (May 16, '06)

Speaker: Alex vardy (UCSD)

Title: "Asymptotic improvements of the Gilbert-Varshamov and
        Minkowski bounds for codes and sphere packings"

Abstract:
---------
  Given positive integers n and d, let A_2(n,d) denote the maximum
size of a binary code of length n and minimum Hamming distance d. The
celebrated result, known as the Gilbert-Varshamov bound, asserts that
A_2(n,d) >= 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) >=  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. Our 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. 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)