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

  Browse A-Z

Log in

Googledetails Microsoftdetails

🔐 Log In

Information on

Subscribing to talksdetails Finding a talkdetails Adding a talkdetails Disseminating talksdetails Help and Documentationdetails

ℹ️ Information

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

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.

This talk is included in these lists:

Note that ex-directory lists are not shown.

Other lists

Hybrid seminar: Clinical School Seminar Room 14 & on Zoom (see Abstract for link) Jasmine meeting room, Microsoft Research Ltd, 7 J J Thomson Avenue (Off Madingley Road), Cambridge Shared facilities C209/210

Other talks

The spread of environmental cost-benefit analysis in UK government, c.1966-1995: representing the public in the Anthropocene Precision psychiatry Geometry and Generalization: The case of Grokking Morning Break Title tbc Dwarf Galaxies in the Local Universe
 

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