Shannon capacity and list decodable codes

Noga Alon.jpg

Noga Alon

Princeton University and Tel Aviv University

Monday, October 28, 2019

Faculty Host
Schachar Lovett



The Shannon capacity of a graph G is an invariant that measures the effective alphabet size of the channel whose confusion graph is G. While this is still a very poorly understood invariant there is some recent progress in the study of parameters that bound it and the relation between them. I will discuss some of these results and will also describe how some of the techniques applied in their proofs are relevant to the study of zero-rate list decodable codes



Noga Alon is a Professor of Mathematics at Princeton University and a Baumritter Professor Emeritus of Mathematics and Computer Science at Tel Aviv University, Israel. He received his PhD in Mathematics at the Hebrew University of Jerusalem and had visiting positions in various research institutes including MIT, the Institute for Advanced Study in Princeton and Microsoft Research.

He is an ACM Fellow and an AMS Fellow, a member of the Israel Academy of Sciences and Humanities and of the Academia Europaea, and an honorary member of the Hungarian Academy of Sciences. He received the Erdos Prize, the Feher Prize, the Polya Prize, the Bruno Memorial Award, the Landau Prize, the Goedel Prize, the Israel Prize, the EMET Prize, the Dijkstra Prize and the Nerode Prize.

His research interests are mainly in Combinatorics, Graph Theory and their applications in Theoretical Computer Science. His main contributions include the study of expander graphs and their applications, the investigation of derandomization techniques, the foundation of streaming algorithms, the development and applications of algebraic and probabilistic methods in Discrete Mathematics and the study of problems in Information Theory, Combinatorial Geometry and Combinatorial Number Theory.