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

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

• Oisín Faust, Cambridge
• Wednesday 21 April 2021, 14:00-15:00
• https://maths-cam-ac-uk.zoom.us/j/95531783868?pwd=U3pPbmYxTXZYRVZMWFBVTkVnWmUvZz09.

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.

This talk is included in these lists:

• CMI Student Seminar Series
• https://maths-cam-ac-uk.zoom.us/j/95531783868?pwd=U3pPbmYxTXZYRVZMWFBVTkVnWmUvZz09

Note that ex-directory lists are not shown.