EPFL

Algo+LMA

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