Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Nathan Klein:

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

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

ISSN 1433-8092 | Imprint