Functional Representation Lemma and Minimum Entropy Coupling

Abstract: The functional representation lemma states that for two jointly-distributed random variables X, Y, it is possible to express Y as a function of X and another random variable Z that is independent of X. There are two interesting extreme points. If we minimize H(Y|Z), the minimum can be bounded by the "strong functional representation lemma", and has implications in lossy compression and channel simulation. If we instead minimize H(Z), this is equivalent to the minimum entropy coupling problem, which concerns finding the coupling of several given distributions that gives the smallest joint entropy. In this talk, we will discuss several recent developments regarding these problems.

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.