11.45, Seminar Hall How many deleted bits can one recover? Venkat Guruswami Carnegie Mellon University, USA. 160818 Abstract Suppose we transmit an nbit string on a channel that can adversarially delete a fraction p of the bits, resulting in a subsequence of length (1p)n received at the other end. What is the largest deletion fraction p for which one can communicate reliably on such a channel at an information rate bounded away from 0? In other words, we would like to encode Omega(n) bits of information into a codeword of n bits that can be recovered from any of its subsequences of length (1p)n. Combinatorially, this property is equivalent to no two codeword sequences sharing a common subsequence of length (1p)n. A rather trivial limit is that we must have p < 1/2 (Why?). It is a tantalizing open question if there exist deletion correcting codes for any p < 1/2. In this talk, we will discuss codes (from joint work with B. Bukh and J. Håstad) that can correct a deletion fraction of 0.414, that too with an efficient algorithm. This remains the best known bound, and beats the previous (nonconstructive) bound of about 0.17. Time permitting, I’ll mention some more recent results about deletion codes in other regimes and models.
