Log-concave polynomials, lattice point counting, and the traveling salesperson problem

Jonathan Leake
University of Waterloo

Log-concave polynomials have been used in recent years to prove various bounds and log-concavity statements. Some well-known examples are: Gurvits' polynomial capacity method for the van der Waerden bound on the permanent, the use of Lorentzian polynomials by Brändén-Huh and Anari-Liu-Oveis Gharan-Vinzant to prove Mason's conjectures, and strongly Rayleigh probability bounds proven by Karlin-Klein-Oveis Gharan to improve the metric TSP approximation factor. In this talk, we will discuss log-concave polynomials and the polynomial capacity method, and we will describe some newer applications of this method. In particular, we will state bounds and approximations for counting lattice points of transportation and flow polytopes, as well as new probability lower bounds for strongly Rayleigh distributions which led to a further improvement to the TSP approximation factor. Joint work with various subsets of Petter Brändén, Leonid Gurvits, Nathan Klein, Alejandro Morales, and Igor Pak.

Back to Workshop II: Integrability and Algebraic Combinatorics