We give a sharp lower bound on the capacity of a homogeneous real stable polynomial, depending only on the value of its gradient at $x = 1$. This result implies a sharp improvement to a similar inequality proved by Linial-Samorodnitsky-Wigderson in 2000, which was crucial to the analysis of their permanent approximation algorithm. Such inequalities have played an important role in the recent work on operator scaling and its generalizations and applications, and in fact we use our bound to construct a new scaling algorithm for real stable polynomials.
In addition, we give a strong improvement on previous lower bounds of the capacity of a non-homogeneous real stable polynomial, depending only on the value of its gradient at $x = 1$. Crucially, this new bound is independent of the degree of the polynomial, and has singly exponential dependence on the number of variables. This compares favorably to the bounds used recently in the fantastic work of Karlin-Klein-Oveis Gharan to give an improved approximation factor for metric TSP, where this dependence is doubly exponential. Such bounds were conjectured to exist by the authors, and thus our new bound should imply further improvement to the approximation factor for metric TSP.
The new technique we develop to prove this bound is productization, which says that any real stable polynomial can be approximated at any point in the positive orthant by a product of linear forms. Beyond the results of this paper, our main hope is that this new technique will allow us to avoid "frightening technicalities", in the words of Laurent and Schrijver, that often accompany combinatorial lower bounds.
Contains a new and improved capacity bound which should imply improvements to the metric TSP results of Karlin-Klein-Oveis Gharan.
The purpose of this note is to state and prove a lower bound on the capacity of a real stable polynomial $p(x)$ which is based only on its value and gradient at $x = 1$. This can be seen as a quantitative generalization of the fact that the capacity of $p$ is maximized when the normalized gradient of $p$ at 1 is equal to 1. This result implies a sharp improvement to a similar inequality proved by Linial-Samorodnitsky-Wigderson in 2000. Such inequalities have played an important role in the recent work on operator scaling and its generalizations and applications. Our bound is also similar to one used very recently by Karlin-Klein-Oveis Gharan to give an improved approximation factor for metric TSP. While our bound does not immediately improve upon theirs, we believe our techniques will help to achieve such an improvement when applied more directly to their situation.
Added some discussion about other aspects of the problem, and we now discuss the connection to metric TSP.
The purpose of this note is to state and prove a lower bound on the capacity of a real stable polynomial $p(x)$ which is based only on its value and gradient at $x=1$. This result implies a sharp improvement to a similar inequality proved by Linial-Samorodnitsky-Wigderson in 2000. Such inequalities have played an important role in the recent work on operator scaling and its generalizations and applications.
