Posted by: atri | March 6, 2013

Lect 22: Converse of Shannon’s theorem for BSC

In today’s lecture we went over the main ideas in the proof of the converse of Shannon’s capacity result for $\mathrm{BSC}_p$. This material is from Section 6.3 in the book. On Friday, we will go over the proof (idea) for the positive part of Shannon’s capacity result, which is also from Section 6.3 in the book.

In class I mentioned a new proof of the Chernoff bound: here is the paper by Russell Impagliazzo and Valentine Kabanets.