ISIT 2014: Janos Körner’s Shannon Lecture

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

T(n) = \max \{ |C| : C \subseteq \{ 0, 1, 2 \}^n,
\forall \{x,y,z\}\ \mathrm{distinct}
\hspace{1in} \exists i\ \mathrm{s.t.} \{x_i, y_i, z_i\} = \{0, 1, 2\} \}

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

\frac{1}{4} \log \frac{9}{5} \le \lim \sup \frac{1}{n} \log T(n) \le \log \frac{3}{2}.

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!