« search calendars« DIMACS Workshop on Entropy and Optimization

« Max Entropy Distributions in (Network) Optimization, Counting and Probability

Max Entropy Distributions in (Network) Optimization, Counting and Probability

May 19, 2022, 1:30 PM - 2:15 PM


Online Event

Shayan Oveis-Gharan, University of Washington

Given a polytope P that is a convex hull of a set of 0-1 vectors (usually of constant hamming weight) and a point x in P, one can write x as a distribution over vertices of P of the largest possible entropy. A decade ago, it has been shown that max entropy distributions can be computed/approximated efficiently for a large class 0-1 polytopes. Consequently, max-entropy distributions found numerous applications in (combinatorial) optimization, counting, and (probabilistic) combinatorics over the last decade. Furthermore, this machinery has led to deep connections between distant fields of Math and Theoretical CS namely approximation algorithms, geometry of polynomials, analysis of Markov chains, Operator theory, etc. In this talk I plan to survey some of these applications and connections. I will also propose several unexplored directions for future research.