An Improved Bound on the Fraction of Correctable Deletions

We will discuss recent progress on code constructions for recovery from worst-case bit deletions. Specifically, we will construct a family of binary codes of positive rate allowing efficient recovery from a fraction of deletions approaching sqrt{2}-1 > 0.414 (though we might focus on a simpler construction for deletion fraction 1/3 for the talk). Previously, even non-constructively the largest deletion fraction known to be correctable with positive rate was around 0.17. For alphabet size k, we construct codes to correct a deletion fraction exceeding (k-1)/(k+1), with (k-1)/k being a trivial upper limit. Whether a deletion fraction approaching 1/2 is correctable by binary codes remains a tantalizing open question. (Joint work with Boris Bukh and Johan Hastad)