Optimization Seminar

Entropy, Optimization and Polynomials

An emerging approach to solve various counting and optimization problems - from computing the permanent of a nonnegative matrix, to the Kadison-Singer problem, to diverse sampling in machine learning - is roughly the following: Formulate the problem as recovering the coefficients of some polynomial and use continuous optimization techniques, along with the analytic structure of the underlying polynomial, to obtain good algorithms. The key quantity that connects the discrete and the continuous worlds is entropy. 

In this talk, I will explain this connection and mention several open problems that lie at the interface of combinatorial optimization, continuous optimization and the analytic theory of polynomials.