Lossless expanders and Information Reconciliation with no shared randomness.

Abstract: Lossless expanders are bipartite graphs in which for every sufficiently small set on the left side of the bipartition, most of the outgoing edges lead to distinct vertices. I will present an application of such graphs in Information Reconciliation. This is a protocol with 2 parties: Sender and Receiver. Sender has a string x and Receiver has a string y. For instance, think that x is an updated version of y. Sender sends a message m which allows Receiver to construct x. The goal is to minimize the length of m, taking into account the correlation of x and y. This correlation can be formalized in different ways and is only known by Receiver. Standard solutions require Sender and Receiver to share randomness. In my talk, I will explain how lossless expanders are used to obtain Information Reconciliation with no shared randomness.

The main idea is from the paper B. Bauwens and M. Zimand, Universal almost optimal compression and Slepian-Wolf coding in probabilistic polynomial time, Journal of the ACM, April 2023 (also available at arXiv:1911.04268), but I'll focus on just one particular aspect.

Computer scienceMathematics

Audience: researchers in the discipline

( paper )

---

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.

---