Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR20-110 | 22nd July 2020 00:30

Capacity Lower Bounds via Productization

RSS-Feed




TR20-110
Authors: Leonid Gurvits, Jonathan Leake
Publication: 22nd July 2020 07:32
Downloads: 102
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