Polynomial Capacity: Theory, Applications, Generalizations
Back home
Course Information
Institution: TU Berlin
Dates: Winter 2020-2021 (starting November)
Time: TBD
Room: Zoom (TBD)
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
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
- Fantastic book: Analytic Theory of Polynomials (by Rahman and Scheisser), 2002.
- Multivariate polynomials
- Applications of stable polynomials
- Beyond stability: log-concave and Lorentzian polynomials
- Applications of log-concave polynomials
- Polynomial Capacity: Theory and Applications
- Polynomial capacity and Gurvits' theorem
- Coefficient bounds
- Linear preservers and capacity
- Other combinatorial applications
- Other algorithmic applications
- Generalizations of Capacity
- Maximum entropy distributions
- Matrix capacity
- Operator scaling: non-commutative polynomial identity testing
- Capacity and invariant theory
- TBD