Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > JONATHAN LEAKE:
All reports by Author Jonathan Leake:

TR23-190 | 15th November 2023
Leonid Gurvits, Nathan Klein, Jonathan Leake

From Trees to Polynomials and Back Again: New Capacity Bounds with Applications to TSP

Revisions: 1

We give simply exponential lower bounds on the probabilities of a given strongly Rayleigh distribution, depending only on its expectation. This resolves a weak version of a problem left open by Karlin-Klein-Oveis Gharan in their recent breakthrough work on metric TSP, and this resolution leads to a minor improvement of ... more >>>


TR20-110 | 22nd July 2020
Leonid Gurvits, Jonathan Leake

Capacity Lower Bounds via Productization

Revisions: 2

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 ... more >>>




ISSN 1433-8092 | Imprint