EPFL

Algo+LMA

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