Information inequalities on graphs with a strong mixing property and their applications.

Abstract: We will discuss the argument of Andrei Muchnik (that goes back to the 1990s) that allows to prove information inequalities specific for neighboring vertices sampled on a graph with a strong mixing property. We will use this technique to show that the classical two-phases protocol of secret key agreement proposed by Ahlswede-Csiszár and Maurer (information reconciliation + privacy amplification) is in some settings the only possible solution. In particular, in the one-shot settings, this protocol is unavoidably asymmetric: (almost) the entire burden of communication falls on one of the protocol participants. (By a joint work with Geoffroy Caillat-Grenier and Rustam Zyavgarov.)

Computer scienceMathematics

Audience: researchers in the discipline

Seminar on Algorithmic Aspects of Information Theory

Series comments: This online seminar is a follow up of the Dagstuhl Seminar 22301, www.dagstuhl.de/en/program/calendar/semhp/?semnr=22301.