Polynomial Capacity and its Applications: To TSP and Beyond

About 20 years ago, Gurvits developed the notion of polynomial capacity to give a simple proof of the famous van der Waerden lower bound on the permanent of a doubly stochastic matrix. Since then, similar techniques have led to various other applications; for example: approximate counting of the lattice points of certain polytopes, an efficient algorithm for the non-commutative version of the polynomial identity testing problem, and most recently, an improved approximation factor for the traveling salesperson problem (TSP) via the max-entropy algorithm.

In this talk, we will discuss polynomial capacity, some of its applications, and its connection to entropy optimization. In particular, we will discuss how we (with Gurvits and Klein) recently used polynomial capacity to further improve the TSP approximation factor.

Joint work with Petter Brändén, Leonid Gurvits, Nathan Klein, Igor Pak, Nisheeth Vishnoi.