|
11.45, Seminar Hall How many deleted bits can one recover? Venkat Guruswami Carnegie Mellon University, USA. 16-08-18 Abstract Suppose we transmit an n-bit string on a channel that can adversarially delete a fraction p of the bits, resulting in a subsequence of length (1-p)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 (1-p)n. Combinatorially, this property is equivalent to no two codeword sequences sharing a common subsequence of length (1-p)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 (non-constructive) bound of about 0.17. Time permitting, I’ll mention some more recent results about deletion codes in other regimes and models.
|
