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

Link to this comparison view

en:group:seminars:20051201 [2009/04/07 12:31]
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 
-==== 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