Title: Matroids and Entropy Functions

Abstract: Matroids and polymatroids are combinatorial structures that encode abstract (in)dependence relations. For instance, the joint entropy function of a finite collection of random variables on a probability space is a polymatroid. This function encodes the dependence relations among the random variables. Lukas Kuehne and I proved that it is undecidable whether a given integer-valued function is a positive multiple of such a joint entropy function. As a consequence, certain natural problems in information theory are undecidable.
In this talk I will discuss matroids and their relation to information theory, and present some undecidability results.


Live broadcast link: https://huji.cloud.panopto.eu/Panopto/Pages/Viewer.aspx?id=dbe01434-ac3e...