# Differences

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

 en:group:seminars:20051201 [2009/04/07 11:17]127.0.0.1 external edit en:group:seminars:20051201 [2016/06/23 11:26] (current) 2009/04/07 12:31 admin 2009/04/07 11:17 external edit Next revision Previous revision 2009/04/07 12:31 admin 2009/04/07 11:17 external edit 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)