The power of non-Shannon inequalities: a short proof of the Gács-Körner theorem.

Abstract: We present a short proof of a celebrated result of Gács and Körner giving sufficient and necessary condition on the joint distribution of two discrete random variables X and Y for the case when their mutual information matches the extractable (in the limit) common information. Our proof is based on the observation that the mere existence of certain random variables jointly distributed with X and Y can impose restrictions on all random variables jointly distributed with X and Y.

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.