This shows you the differences between two versions of the page.
| Next revision | Previous revision | ||
|
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) |
||
|---|---|---|---|
| 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) | ||