Janos Körner’s Shannon lecture was “On the Mathematics of Distinguishable Difference.” He began by remarking how information theory in Hungary was really a branch of mathematics — at least that’s how Rényi viewed it — and how collaborations made him appreciate some of the operational significance of information problems. On the other hand, he also made a strong case for understanding the combinatorial structure of many problems abstractly. A simple motivating example was something he called “trifference.” Basically he is asking for

That’s a mouthful! We want a set of trinary codewords such that any triple of codewords differs in at a least one position. What’s the maximum size of such a set? That’s . More specifically, we want the rate of growth of this thing. That we have are upper and lower bounds:

.

It turns out that simple i.i.d. random coding is not going to give you a good set — the lower bound comes from a non-uniform random codebook. The upper bound is actually a capacity of a hypergraph. This led him to his second topic, which was on hypergraph entropy, a generalization of graph entropy. This is connected to Sperner families of subsets: collections such that for any pair of subsets, neither contains the other. The rate of growth of Sperner families is also related to the hypergraph entropy.

I didn’t really manage to take as good notes as I might have wanted, but I really enjoyed the lecture, and you can too, now that the video has been posted on the IT Society website. I heard some people complaining that the talk was a little too technical while walking out of the plenary hall, but for me, it was quite clear and quite interesting, even at 8:30 in the morning. You can’t please everyone I guess!