Date: Feb 12, 2016 11:00am - 12:00pm
Location: POB 2.402
Talk Audience: Faculty, Graduate Students, ECE and math faculty/graduate students
Host: David Zuckerman
Talk Abstract: This talk will discuss recent progress on code constructions for recovery from worst-case bit deletions.
The first part will consider the case of a large fraction of deletions, where we construct a family of binary codes of positive rate to recover from a fraction of deletions approaching 1/3. Previously, even non-constructively the largest deletion fraction known to be correctable with positive rate was around 0.17. For alphabet size k, we are able to correct a deletion fraction approaching (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.)
The second part will consider the other noise regime, of correcting from a small... Read more