2009 ISIT Plenary Lecture
Combinatorial Reasoning in Information Theory
Professor Noga Alon
Tel Aviv University
Combinatorial arguments have played a crucial role in the investigation of several surprising phenomena in Information Theory. I will discuss some of these results focusing on a recent example, based on joint papers with Lubetzky and Stav, and with Hassidim and Weinstein, in which properties of graph powers, colorings of Cayley graphs, and the chromatic numbers of Kneser graphs are applied in the study of a broadcasting problem with side information.