Revisiting combinatorial applications of information inequalities.

Abstract: This (short) talk is a reaction to Dan Suciu's talk of the last year. He showed some new combinatorial inequalities that use L_p-size of sections of some sets. One could note that they have Kolmogorov complexity versions (even a bit more general that give a bound for the pair (C(x),C(y|x)) in terms of the section size statistics), and it would be interesting to find out whether one can get a similar bound for Shannon's entropies.

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.