Abstract
Real stable polynomials have recently found many applications, some of which include the resolution of the Kadison-Singer problem, a new proof of the Van der Waerden conjecture, and several applications to variants of the traveling salesman problem. In this talk I will survey some more recent algorithmic applications of these polynomials and the intimately connected strongly Rayleigh measures.
Strongly Rayleigh (SR) measures are discrete measures (traditionally, on the vertices of the hypercube) defined in terms of the zeros of their multivariate generating polynomials. They satisfy one of the strongest forms of negative dependence, and are closed under several important operations, including marginalization, conditioning, and convolutions. They include well-studied families: collections of independent Bernoullis, random spanning trees, and determinantal point processes. They are also closely related to matroids, and can often be thought of as weighted matroids.
I will explain some of the connections and similarities of the SR measures to their continuous cousins, log-concave functions: Namely the similarities of their analytic structure, and their tractability for the problems of (approximate) counting and optimization.
I will then show how stable polynomials can go beyond negative dependence and also capture some forms of positive dependence. Algorithmic tractability of the extended family of measures enables us to obtain approximation algorithms for several problems, examples of which include: Computing the permanent of nonnegative matrices, maximizing Nash social welfare, and constrained volume maximization. I will show how negative and positive dependence are used to derive these results.
Time-permitting, I will conclude with some open problems:
- Resolving the Van der Waerden conjecture for non-bipartite graphs using real stable polynomials.
- Finding efficient rounding methods for the optimization applications, preserving approximation guarantees.
- Explaining the connection between mixed characteristic polynomials and point-wise products of SR measures by perhaps using Marcus-Spielman-Srivastava’s barrier arguments as a bridge.
Based on joint works with Shayan Oveis Gharan, Alireza Rezaei, Amin Saberi, and Mohit Singh.