BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:A Survey of Results for Deletion Channels and Related Synchronizat
 ion Channels - Michael Mitzenmacher\, Harvard University
DTSTART:20090224T140000Z
DTEND:20090224T153000Z
UID:TALK13968@talks.cam.ac.uk
CONTACT:Neil Walton
DESCRIPTION:At this point\, it seems that most everything is known about t
 he basic channels studied in\ninformation theory. For the i.i.d. (independ
 ent and identically distributed) binary\nerasure channel and the i.i.d. bi
 nary symmetric error channel\, the capacity has long been\nknown\, and the
 re are very efficient encoding and decoding schemes that are near capacity
 .\n\nThe situation is very different for the i.i.d. binary deletion channe
 l. With this\nchannel\, the sender sends n bits\, and each bit is deleted 
 with some fixed probability p.\nSo\, for example\, the sender might send 1
 0110010\, and the receiver obtains 1100. The\ni.i.d. binary deletion chann
 el is perhaps the most basic channel that incorporates the\nchallenge of s
 ynchronization. Surprisingly\, even the capacity of the deletion channel\n
 remains unknown!\n\nIn this talk\, I will survey what is known about the d
 eletion channel\, focusing on our\nrecent work on bounds on the capacity. 
 The main result is that the for any probability p\,\nthe deletion channel 
 has capacity at least (1-p)/9. Hence\, the capacity of the deletion\nchann
 el is always within a constant factor of the erasure channel (which has ca
 pacity\n(1-p)). We also discuss the many remaining open problems in the ar
 ea of synchronization\nchannels.\n\nNo previous background is necessary.\n
 \n
LOCATION:MR5\, CMS\, Wilberforce Road\, Cambridge\, CB3 0WB
END:VEVENT
END:VCALENDAR