Videos

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

Presenter
April 17, 2024
Abstract
Recorded 17 April 2024. Jonathan Leake of the University of Waterloo presents "Log-concave polynomials, lattice point counting, and the traveling salesperson problem" at IPAM's Integrability and Algebraic Combinatorics Workshop. Abstract: 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. Learn more online at: https://www.ipam.ucla.edu/programs/workshops/workshop-ii-integrability-and-algebraic-combinatorics/