New Results and Open Problems for Deletion Channels
Michael Mitzenmacher, Harvard University
At this point, it seems that most everything is known about the basic channels studied in information theory. For the i.i.d. (independent and identically distributed) binary erasure channel and the i.i.d. binary symmetric error channel, the capacity has long been known, and there are very efficient encoding and decoding schemes that are near capacity.
The situation is very different for the i.i.d. binary deletion channel. With this channel, the sender sends n bits, and each bit is deleted with some fixed probability p. So, for example, the sender might send 10110010, and the receiver obtains 1100. The i.i.d. binary deletion channel is perhaps the most basic channel that incorporates the challenge of synchronization. Surprisingly, even the capacity of the deletion channel remains unknown!
In this talk, I will survey what is known about the deletion channel, focusing on our work on bounds on the capacity and on the many remaining open problems that seem well suited to our community.
No previous background is required.
Joint work with Eleni Drinea.
