COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

University of Cambridge > Talks.cam > Optimization and Incentives Seminar > A Survey of Results for Deletion Channels and Related Synchronization Channels

## A Survey of Results for Deletion Channels and Related Synchronization ChannelsAdd to your list(s) Download to your calendar using vCal - Michael Mitzenmacher, Harvard University
- Tuesday 24 February 2009, 14:00-15:30
- MR5, CMS, Wilberforce Road, Cambridge, CB3 0WB.
If you have a question about this talk, please contact Neil Walton. Joint With Probability Seminar Series. 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 recent work on bounds on the capacity. The main result is that the for any probability p, the deletion channel has capacity at least (1-p)/9. Hence, the capacity of the deletion channel is always 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 synchronization channels. No previous background is necessary. This talk is part of the Optimization and Incentives Seminar series. ## This talk is included in these lists:- All CMS events
- All Cavendish Laboratory Seminars
- All Talks (aka the CURE list)
- Biology
- CMS Events
- Cambridge Neuroscience Seminars
- Cambridge talks
- Centre for Health Leadership and Enterprise
- Chris Davis' list
- DPMMS Lists
- DPMMS info aggregator
- DPMMS lists
- Economics and Computer Science Talks
- Featured lists
- Guy Emerson's list
- Hanchen DaDaDash
- Inference Group
- Inference Group Summary
- Interested Talks
- Joint Machine Learning Seminars
- Life Science
- Life Sciences
- ME Seminar
- ML
- MR5, CMS, Wilberforce Road, Cambridge, CB3 0WB
- Machine Learning Summary
- Neurons, Fake News, DNA and your iPhone: The Mathematics of Information
- Neuroscience
- Neuroscience Seminars
- Neuroscience Seminars
- Optimization and Incentives Seminar
- Required lists for MLG
- School of Physical Sciences
- Statistical Laboratory info aggregator
- Stem Cells & Regenerative Medicine
- Thin Film Magnetic Talks
- Trust & Technology Initiative - interesting events
- bld31
- dh539
- rp587
- yk373's list
Note that ex-directory lists are not shown. |
## Other listsAndrew Thomason Entrepreneurship Centre at Cambridge Judge Business School Type the title of a new list here## Other talksSatellite Observations for Climate Resilience and Sustainability The importance of seed testing Dynamics of Phenotypic and Genomic Evolution in a Long-Term Experiment with E. coli Player 2 has entered the game - ways of working towards open science Exploring the mechanisms of haematopoietic lineage progression at the single-cell level Strong Bonds, Affective Labour: Sexually Transmitted Infections and the Work of History |