Seminar on Algorithmic Aspects of Information Theory

This is a page of the online seminar on algorithmic aspects of information theory, a follow up of Dagstuhl Seminar 22301.

Upcoming meetings:

• 01 February 2023, 8h-9h15am Pacific / 5h-6h15pm CET : Alexander Kozachinskiy (Catholic University of Chile)
  Title: On the recent progress on Frankl's conjecture.
  Abstract: Frankl's conjecture states that for any non-empty family of non-empty finite sets which is closed under finite union there exists an element belonging to at least 1/2 of the sets from the family. I will present a recent result of Gilmer that this conjecture holds for some positive constant.
  Zoom link: https://cnrs.zoom.us/j/99572181348?pwd=WmNEZnBRVGFndk5zQnMzeGxMcnJ6QT09 (Meeting ID: 995 7218 1348, Passcode: 7QtJF3)
• 15 March 2023, 8h-9h15am Pacific / 5h-6h15pm CET : Vlad Demartsev (Max Planck Institute of Animal Behavior)
  Title: TBA

Past meetings:

• 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.
  slides video
• 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.
  slides video
• 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.
  slides video
  Bibliography: Zhen Zhang and Raymond W. Yeung. On Characterization of Entropy Function via Information Inequalities. IEEE Transactions on Information Theory, 44(4), 1440-1452.
• 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.
  slides video
  Bibliography: Frantisek Matus. Infinitely many information inequalities. IEEE International Symposium on Information Theory 2007, pp. 41-44.
• 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
  video
• 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.
  slides video
• 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).
  slides video

If you want to add your address to the mailing list please contact us