Differences

This shows you the differences between two versions of the page.

Link to this comparison view

en:group:seminars:20051201 [2009/04/07 11:17]
127.0.0.1 external edit
en:group:seminars:20051201 [2009/04/07 12:31]
admin
Line 15: Line 15:
 ==== abstract ==== ==== abstract ====
 Given positive integers $n$ and $d$, let $A_2(n,d)$ denote the maximum i 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)