Common information in well-mixing graphs and applications to information-theoretic cryptography

Geoffroy Caillat-Grenier, Andrei Romashchenko, Rustam Zyavgarov

We study the connection between mixing properties for bipartite graphs and materialization of the mutual information in one-shot settings. We show that mixing properties of a graph…