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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: