Showing cs.ITShow all
2 papers · 1 filter
cs.IT2024
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…
cs.IT2023
Spectral approach to the communication complexity of multi-party key agreement
Geoffroy Caillat-Grenier, Andrei Romashchenko
We propose a linear algebraic method, rooted in the spectral properties of graphs, that can be used to prove lower bounds in communication complexity. Our proof technique effective…