Open Collections

What fraction of worst-case bit deletions are correctable?

Banff International Research Station for Mathematical Innovation and Discovery

We will discuss recent code constructions for recovery from a large fraction of 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)

Mathematics; Computer science; Theoretical computer science

video/mp4

Author affiliation: Carnegie Mellon University

2017-03-07

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/60804

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/