Selected Topics in Algorithms and Optimization: Geometry of polynomials and algorithmic applications
Lecturer: Dr. Wenzheng Li
Many central questions in combinatorics and optimization concern probability distributions over discrete objects, such as matchings, spanning trees, and matroid bases. A powerful way to study these distributions is to encode the objects and their weights in multivariate generating polynomials. Properties of these polynomials, such as zero-free regions, log-concavity, and Hessian signatures, can help us understand the distributions and reveal structure in the underlying discrete problems. This viewpoint connects combinatorics and optimization with complex analysis, convex geometry, and probability.
This course introduces the geometry of polynomials with an emphasis on algorithmic applications. We will begin with maximum-entropy convex programs and Gurvits’s capacity method, developing the theory of real stable and completely log-concave polynomials along the way. Applications will include Nash social welfare maximization, determinant maximization, approximation algorithms for the traveling salesman problem (TSP), and counting problems such as estimating permanents and the number of matroid bases.
Further topics may include zero-free regions of independence polynomials and their connection to the Lovász Local Lemma, as well as interlacing families and the Marcus–Spielman–Srivastava proof of the Kadison–Singer problem. If time permits, we will also explore connections between log-concavity and efficient counting and sampling.
For an overview of the topics and further reading, see the following courses and references:
* Shayan Oveis Gharan. Polynomial Paradigm in Algorithm Design. CSE 599, University of Washington, 2020.
* Jan Vondrák. Geometry of Polynomials and Non-Constructive Proofs in Combinatorics. MATH 233A, Stanford University, 2018.
* Nathan Klein. The Geometry of Polynomials in Algorithms. CS 599, Boston University, 2026.
* Jonathan Leake. [*Lorentzian Polynomials (and Polynomial Capacity)*] CO 739, University of Waterloo, 2023.
* Nikhil Srivastava. The Geometry of Polynomials in Algorithms, Combinatorics, and Probability. Math 270, University of California, Berkeley, 2015.
* Nikhil Bansal, Wenzheng Li, Mohit Singh, and Yuze Xu. Iterative Rounding for Determinant Maximization and Real Stable PolynomialsPreprint.
Dates
TBD