Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR20-110 | 22nd September 2022 04:54

Capacity Lower Bounds via Productization

RSS-Feed




Revision #2
Authors: Leonid Gurvits, Jonathan Leake
Accepted on: 22nd September 2022 04:54
Downloads: 97
Keywords: 


Abstract:

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.



Changes to previous version:

Contains a new and improved capacity bound which should imply improvements to the metric TSP results of Karlin-Klein-Oveis Gharan.


Revision #1 to TR20-110 | 8th September 2020 22:35

Capacity Lower Bounds via Productization





Revision #1
Authors: Leonid Gurvits, Jonathan Leake
Accepted on: 8th September 2020 22:35
Downloads: 274
Keywords: 


Abstract:

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.



Changes to previous version:

Added some discussion about other aspects of the problem, and we now discuss the connection to metric TSP.


Paper:

TR20-110 | 22nd July 2020 00:30

Capacity Lower Bounds via Productization





TR20-110
Authors: Leonid Gurvits, Jonathan Leake
Publication: 22nd July 2020 07:32
Downloads: 505
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint