---- dataentry seminar ----
date_dt : 2005-12-01
title : Asymptotic Improvements of the Gilbert-Varshamov  and Minkowski Bounds for 
speaker : Professor Alex Vardy
affiliation :  UC San Diego
time : 
room : 
table : seminars
===================
template:datatemplates:seminar
-----------------------


==== abstract ====
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)