A Survey of Results for the Deletion Channel and Related Synchronization Channels
Oct 11, 2010
from 12:30 PM to 01:30 PM
|Add event to calendar||
Monday, October 11, 2010 at 12:30PM
54-134 Engineering IV Building
Abstract: 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$.
Biography: Michael Mitzenmacher is a Professor of Computer Science in the School of Engineering and Applied Sciences at Harvard University. Michael has authored or co-authored over 150 conference and journal publications on a variety of topics, with a focus on algorithms for networks and the Internet. His work on low-density parity-check codes shared the 2002 IEEE Information Theory Society Best Paper Award and the 2009 ACM SIGCOMM Test of Time Award. His textbook on random algorithms and probabilistic analysis in computer science was published in 2005 by Cambridge University Press. Michael Mitzenmacher graduated summa cum laude with a degree in mathematics and computer science from Harvard in 1991. After studying math for a year in Cambridge, England, on the Churchill Scholarship, he obtained his Ph. D. in computer science at U.C. Berkeley in 1996. He then worked at Digital Systems Research Center until joining the Harvard faculty in 1999.