This is a page of the online seminar on algorithmic aspects of information theory,
a follow up of Dagstuhl Seminar 22301.
-
12 October 2022, 8h-9h15am Pacific / 5h-6h15pm CET :
Laszlo Csirmaz (Central European University, Budapest).
Around entropy inequalities.
Abstract: This will be an introductory talk on linear inequalities for Shannon's entropy:
what the problem is, what the methods are, what is known and what is not known.
-
26 October 2022, 8h-9h15am Pacific / 5h-6h15pm CET :
Andrei Romashchenko (CNRS LIRMM, Montpellier).
Basic proof techniques for entropic inequalities.
Abstract: We will consider again several classical theorems mentioned in the survey by
Laszlo Csirmaz
(the first lecture) and discuss the proof techniques behind these results.
-
9 November 2022, 8h-9h15am Pacific / 5h-6h15pm CET :
Andrei Romashchenko (CNRS LIRMM, Montpellier).
The Zhang-Yeung inequality: an attempt to explain.
Abstract: We will discuss a magical proof of the first example of a non-Shannon type inequality
(Zhang-Yeung'1998) and try to explain how this and similar arguments could be invented without magic.
-
23 November 2022, 8h-9h15am Pacific / 5h-6h15pm CET :
Laszlo Csirmaz (Central European University, Budapest). The entropy region is not polyhedra.
Abstract: We present the two ingredients of the proof: a set of
entropy inequalities and a collection of sample distributions,
and how these yield the famous result of Fero Matus.
If time permits, we sketch the proof of the used inequalities, and
indicate the shortcomings of other applications of the same idea.
-
7 December 2022, 8h-9h15am Pacific / 5h-6h15pm CET :
Alexander Shen (CNRS LIRMM, Montpellier). Information inequalities: combinatorial interpretation.
Abstract:
Information inequalities like H(A,B) ≤ H(A)+H(B) or H(A)+H(A,B,C) ≤ H(A,B)+H(A,C) have natural interpretation. It is enough to check them for "uniform" random variables that can be constructed starting from a group and its subgroups (Chan,Yeung). On the other hand, they can be translated to Kolmogorov complexity language. Combining these tools, one can get a combinatorial characterization of the class of information inequalities
-
04 January 2023, 8h-9h15am Pacific / 5h-6h15pm CET : Frederique Elise Oggier (Nanyang Technological University, Singapore),
An overview of Ingleton's inequality from a group theory point of view.
Abstract: We will review several works that use group theory to approach Ingleton's inequality and entropic vectors.
-
18 January 2023, 8h-9h15am Pacific / 5h-6h15pm CET : LI Cheuk Ting (Chinese University of Hong Kong),
Title: 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).