Abstract

In this talk I will showcase some applications of hyperbolic, and more generally log-concave, polynomials to discrete optimization problems. I will present a framework for approximately finding the maximum of a discrete function on the hypercube as long as this function is associated with coefficients of a log-concave polynomial. I will also discuss finding the maximum of a mixture of function values. Some specific problems solved by this framework include Nash welfare maximization, and determinant/volume maximization subject to a matroid constraint. Based on joint works with Shayan Oveis Gharan, Kuikui Liu, Amin Saberi, Mohit Singh, and Cynthia Vinzant.

Video Recording