Description:

Title: The geometry of entropy functions

Abstract: Given a collection of N random variables on a finite probability space, we can consider their joint entropy function. This is a real-valued function H on P({1,...,N}) that measures dependencies between the variables. It is natural to ask which functions can be obtained in this way: how can we tell whether a given function H is a joint entropy function? What are the constraints on the set of possible H? These questions can be turned into decision problems. Some variants are undecidable, and several others are not well understood. These problems arise in contexts such as bounding the output size of database queries and designing cryptographic secret sharing schemes.
After defining the terms, we will sketch some of what is known, outline a connection to synthetic geometry, and discuss several open problems. Background in information theory will not be assumed.
Parts of this talk are based on joint work with Lukas Kühne.