3 papers
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…
math.CO2023
Random Schreier graphs as expanders
Geoffroy Caillat-Grenier
Expander graphs, due to their mixing properties, are useful in many algorithms and combinatorial constructions. One can produce an expander graph with high probability by taking a…
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…