# Differences

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

 en:group:seminars:20051201 [2009/04/07 12:31]admin en:group:seminars:20051201 [2016/06/23 11:26] Line 1: Line 1: - - ---- 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)