Shayan Oveis-Gharan, University of Washington

Abstract

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.