2014 Shannon Lecture: On The Mathematics of Distinguishable Difference.
By János Körner, "Sapienza" University of Rome
We explore the interplay of Shannon theory with extremal combinatorics.
In the early eighties the author came to the conclusion that the problem of separate encoding of two correlated binary sources for the recovery of their binary sum is a true stumbling block in multi-user information theory and began a quest for new combinatorial tools to face this challenge. Although the problem of the binary sum remains unsolved in the case of general joint distributions, many intriguing problems in combinatorics could be solved using information-theoretic methods and the hope remains that the construction of a bridge between these two fields will eventually bring returns to mainstream information theory.