Back home
Course Information
Institution: TU Berlin
Dates: Winter 2020-2021 (starting November 5th)
Time: Thursdays, 16:15-17:45 CET (4:15-5:45 PM central European time)
Room: Zoom (contact me for the link)
Description
Since its birth around 15 years ago, polynomial capacity has seen a number of applications and generalizations in
- Combinatorics (e.g., counting matchings in a bipartite graph, counting contingency tables),
- Approximation algorithms (e.g. for the permanent, the mixed discriminant, the intersection of two matroids),
- Optimization (e.g., computing maximum entropy distributions, optimization on manifolds),
- Invariant theory (e.g., matrix scaling, tensor scaling, null-cone problems),
and beyond. Throughout the course we will investigate and unify the many applications of capacity already in the literature, before turning to the recent generalizations and new interpretations of capacity. Although the notion of capacity is itself quite new, its power comes in the simplicity of its use, and we will see this theme play out over the whole of the course. In particular, nothing beyond an undergraduate knowledge of linear algebra, calculus, complex analysis, and some basic graph theory will be required for most of our applications. (The last part of the course may require at various points some basic knowledge of optimization theory, invariant theory, Lie theory, etc.)
The course will have three parts. In the first part, we will study the theory of real-rooted and stable polynomials as well as the recent generalization of these classes to Lorentzian polynomials (also called strongly/completely log-concave). We will focus mainly on the important log-concavity properties of these classes. In the second part, I will introduce the notion of polynomial capacity and demonstrate the interplay between capacity and the various polynomial classes. Along the way we will consider the many known mathematics and computer science applications of capacity. In the third part, we will explore a number of generalizations and different interpretations of the notion of capacity. Here we will dive deeper into the entropic, invariant-theoretic, and optimization-theoretic features of capacity, and this part of the course will be much more exploratory and open-ended.
Outline and References
Below is an expanded outline of the course, with various references to the literature. The reference lists given here are by no means comprehensive, and I have usually chosen to provide the most modern and up-to-date references. Those interested in the history of the literature on these subjects should consult the references within the references given below, or ask me about it. This outline and the associated references will be updated over the course of the semester, and various course materials such and notes and slides will be added to this page as they become available.
- Theory of Stable Polynomials
- Univariate polynomials [slides, exercises]
- Multivariate polynomials [slides, exercises]
- Applications of stable polynomials (without polynomial capacity) [slides]
- The Lee-Yang and Pólya-Schur programs II: Theory of stable polynomials and applications (Borcea and Brändén), 2009.
- Homogeneous multivariate polynomials with the half-plane property (Choe, Oxley, Sokal, and Wagner), 2004.
- The multivariate Tutte polynomial (alias Potts model) for graphs and matroids (Sokal), 2005.
- The roots of the independence polynomial of a claw-free graph (Chudnovsky and Seymour), 2007.
- Theory of monomer-dimer systems (Heilmann and Lieb), 1972.
- Hyperbolicity and stable polynomials in combinatorics and probability (Pemantle), 2012.
- Negative dependence and the geometry of polynomials (Borcea, Brändén, and Liggett), 2009.
- Interlacing families II: Mixed characteristic polynomials and the Kadison-Singer problem (Marcus, Spielman, and Srivastava), 2015.
- Many more...
- Beyond stability: log-concave and Lorentzian polynomials [slides, exercises]
- Applications of log-concave polynomials [slides, exercises]
- Lorentzian Polynomials (Brändén and Huh), 2019.
- Log-concave polynomials I: Entropy and a deterministic approximation algorithm for counting bases of matroids (Anari, Oveis Gharan, and Vinzant), 2018.
- Log-concave polynomials II: High-dimensional walks and an FPRAS for counting bases of a matroid (Anari, Liu, Oveis Gharan, and Vinzant), 2019.
- Log-concave polynomials III: Mason's ultra-log-concavity conjecture for independent sets of matroids (Anari, Liu, Oveis Gharan, and Vinzant), 2018.
- Logarithmic concavity of Schur and related polynomials (Huh, Matherne, Mészáros, and Dizier), 2019.
- Hodge-Riemann relations for Potts model partition functions (Brändén and Huh), 2019.
- Log-concave and unimodal sequences in algebra, combinatorics, and geometry (Stanley), 1989.
- Unimodality, log-concavity, real-rootedness and beyond (Brändén), 2014.
- Polynomial Capacity: Theory and Applications
- Polynomial capacity and Gurvits' theorem [slides, exercises]
- Coefficient bounds [slides]
- Coefficient bounds recap (after holiday break) [slides, exercises]
- General capacity bounds for inner products and linear preservers [slides, exercises]
- Applications of the general capacity bounds [slides]
- Generalizations of Capacity
- Capacity and maximum entropy distributions [slides]
- Maximum entropy distributions on unitary orbits [slides]
- Capacity and scaling algorithms [slides]
- A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents (Linial, Samorodnitsky, and Wigderson), 2000.
- Operator scaling: Theory and applications (Garg, Gurvits, Oliveira, and Wigderson), 2015.
- Operator scaling with specified marginals (Franks), 2018.
- Much faster algorithms for matrix scaling (Allen-Zhu, Li, Oliveira, and Wigderson).
- Efficient algorithms for tensor scaling, quantum marginals and moment polytopes (Bürgisser, Franks, Garg, Oliveira, Walter, and Wigderson), 2018.
- Operator scaling via geodesically convex optimization, invariant theory and polynomial identity testing (Allen-Zhu, Garg, Li, Oliveira, and Wigderson), 2018.
- Quantum algorithms for matrix scaling and matrix balancing (van Apeldoorn, Gribling, Li, Nieuwboer, Walter, and de Wolf), 2020.
- Interior-point methods for unconstrained geometric programming and scaling problems (Bürgisser, Li, Nieuwboer, and Walter), 2020.
- Capacity and invariant theory [slides]
- Towards a theory of non-commutative optimization: Geodesic first and second order methods for moment maps and polytopes (Bürgisser, Franks, Garg, Oliveira, Walter, and Wigderson), 2019.
- Minimal length in an orbit closure as a semiclassical limit (Franks and Walter), 2020.
- Alternating minimization, scaling algorithms, and the null-cone problem from invariant theory (Bürgisser, Garg, Oliveira, Walter, and Wigderson), 2017.
- Invariant theory and scaling algorithms for maximum likelihood estimation (Améndola, Kohn, Peichenback, and Seigal), 2020.
- Operator scaling via geodesically convex optimization, invariant theory and polynomial identity testing (Allen-Zhu, Garg, Li, Oliveira, and Wigderson), 2018.
- Barriers for recent methods in geodesic optimization (Franks and Reichenbach), 2021.
- Capacity recap: All the forms of capacity [slides]