University of Cambridge > Talks.cam > CMI Student Seminar Series > Information, Graphs, Optimization: the Lovász bound on the Shannon capacity

Information, Graphs, Optimization: the Lovász bound on the Shannon capacity

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Dominic Wynter.

How efficiently can one communicate over a noisy channel in a reliable (zero error) way? This was asked, and in many ways answered, by Claude Shannon shortly after he invented information theory. The efficiency value Shannon defined remains elusive today: it is a graph-theoretic parameter which we know how to compute only for very special channels. Fortunately, it has a very nice, efficiently computable upper bound which is due to László Lovász.

I will give a brief introduction to these ideas, which I believe many in the CMI community might find interesting. It is my intention that a few elementary notions from graph theory and linear algebra should be enough to follow this talk.

This talk is part of the CMI Student Seminar Series series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2021 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity