A Survey of Results for Deletion Channels and Related Synchronization Channels

ACO Colloquium
Wednesday, January 21, 2009 - 4:30pm for 2 hours
Michael Mitzenmacher – Harvard University
Robin Thomas
We describe recent progress in the study of the binary deletion channel and related channels with synchronization errors, including a clear description of many open problems in this area. As an example, while the capacity of the binary symmetric error channel and the binary erasure channel have been known since Shannon, we still do not have a closed-form description of the capacity of the binary deletion channel. We highlight a recent result that shows that the capacity is at least (1-p)/9 when each bit is deleted independently with fixed probability p.