All reports by Author Boris Bukh:

__
TR15-117
| 21st July 2015
__

Boris Bukh, Venkatesan Guruswami#### An improved bound on the fraction of correctable deletions

Revisions: 1

Boris Bukh, Venkatesan Guruswami

We consider codes over fixed alphabets against worst-case symbol deletions. For any fixed $k \ge 2$, we construct a family of codes over alphabet of size $k$ with positive rate, which allow efficient recovery from a worst-case deletion fraction approaching $1-\frac{2}{k+1}$. In particular, for binary codes, we are able to ... more >>>