Theory seminar: Computability of Maximum Entropy Distributions and Counting Problems

Tuesday, May 12, 2015 -
11:00am to 12:00pm
CS 4310

Speaker Name: 

Mohit Singh

Speaker Institution: 

Microsoft Research Redmond




In this talk I will discuss the problem of computing max-entropy distributions over a discrete set of objects subject to observed marginals. For instance, given a weighted bipartite graph, can we compute a probability distribution over the set of perfect matchings in the graph whose marginals are the edge weights which maximizes the entropy?

While there has been a tremendous amount of interest in such distributions due to their applicability in areas such as statistical physics, economics, biology, information theory, machine learning, combinatorics and algorithms, a rigorous and systematic study of how to compute such distributions has been lacking. In this talk, I will discuss the challenges in the computability of max-entropy distributions and show that the problem, in a fairly general setting, is equivalent to a counting problem on the underlying set. As one consequence, for several combinatorial settings, there is an efficient algorithm to compute max-entropy distributions.

This is joint work with Nisheeth Vishnoi.