Abstract
We present a new general lower bound on the capacity of a homogeneous real stable polynomial, which depends only on the value and the gradient of the polynomial at the all-ones vector. This bound has two purposes. First, our bound constitutes a sharp improvement of a similar bound obtained by Linial, Samorodnitsky, and Wigderson in their 2000 paper on matrix scaling and approximating the permanent. Such bounds have also played an important role in more recent work on operator scaling and its generalizations and applications. Second, a very recent paper of Karlin, Klein, and Oveis Gharan use bounds of a similar spirit to obtain an improved approximation factor for metric TSP. Our bound improves upon theirs in various cases, but the precise connection between the bounds in full generality is currently unclear. In this talk we will state and sketch the proof of our bound, and we will also discuss these applications with particular focus on the connection to the recent work on metric TSP. (This is joint work with Leonid Gurvits.)