ECCC-Report TR20-110https://eccc.weizmann.ac.il/report/2020/110Comments and Revisions published for TR20-110en-usThu, 22 Sep 2022 04:54:36 +0300
Revision 2
| Capacity Lower Bounds via Productization |
Leonid Gurvits,
Jonathan Leake
https://eccc.weizmann.ac.il/report/2020/110#revision2We 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.Thu, 22 Sep 2022 04:54:36 +0300https://eccc.weizmann.ac.il/report/2020/110#revision2
Revision 1
| Capacity Lower Bounds via Productization |
Leonid Gurvits,
Jonathan Leake
https://eccc.weizmann.ac.il/report/2020/110#revision1The 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.Tue, 08 Sep 2020 22:35:03 +0300https://eccc.weizmann.ac.il/report/2020/110#revision1
Paper TR20-110
| Capacity Lower Bounds via Productization |
Leonid Gurvits,
Jonathan Leake
https://eccc.weizmann.ac.il/report/2020/110The 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.Wed, 22 Jul 2020 07:32:00 +0300https://eccc.weizmann.ac.il/report/2020/110