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 #1 to TR20-110 | 8th September 2020 22:35

Capacity Lower Bounds via Productization

RSS-Feed




Revision #1
Authors: Leonid Gurvits, Jonathan Leake
Accepted on: 8th September 2020 22:35
Downloads: 6
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: 133
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