Colloquium: Geva Yashfe (Tzafriri lecture)

Thu, 10/03/202214:30-16:00
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: