Existential information inequalities, non-Shannon inequalities, and automated theorem proving.

Abstract: Existential information inequality is a generalization of linear information inequalities, where random variables can not only be universally quantified, but also existentially quantified. We study the structure of existential information inequalities, and describe algorithms for automated verification of existential information inequalities, which are also useful for proving (non-existential) non-Shannon inequalities. We also describe how a wide range of results in network information theory (e.g. 32 out of 56 theorems in Chapters 1-14 of Network Information Theory by El Gamal and Kim) can be proved automatically using the proposed algorithms. The algorithms are implemented in the PSITIP framework ( github.com/cheuktingli/psitip ).

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.