An improved bound on the fraction of correctable deletions

Boris Bukh, Venkatesan Guruswami, Johan Håstad

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, wh…