BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:JOINT WITH NETWORKS (OR)  SEMINAR SERIES:A Survey of Results for D
 eletion Channels and Related Synchronization Channels - Michael Mitzenmach
 er\, Harvard University
DTSTART:20090224T140000Z
DTEND:20090224T150000Z
UID:TALK17089@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 information theory. For the i.i.d. (independe
 nt and identically distributed) binary erasure channel and the i.i.d. bina
 ry symmetric error channel\, the capacity has long been known\, and there 
 are very efficient encoding and decoding schemes that are near capacity.\n
 \nThe 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 101100
 10\, and the receiver obtains 1100. The i.i.d. binary deletion channel is 
 perhaps the most basic channel that incorporates the challenge of synchron
 ization. Surprisingly\, even the capacity of the deletion channel remains 
 unknown!\n\nIn this talk\, I will survey what is known about the deletion 
 channel\, focusing on our recent work on bounds on the capacity. The main 
 result is that the for any probability p\, the deletion channel has capaci
 ty at least (1-p)/9. Hence\, the capacity of the deletion channel is alway
 s within a constant factor of the erasure channel (which has capacity (1-p
 )). We also discuss the many remaining open problems in the area of synchr
 onization channels.\n\nNo previous background is necessary.\n\n
LOCATION:MR12\, CMS\, Wilberforce Road\, Cambridge\, CB3 0WB
END:VEVENT
END:VCALENDAR