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

Leonid Gurvits, Nathan Klein, Jonathan Leake

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…