Polynomial Capacity: Theory, Applications, Generalizations

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.

1. Theory of stable, log-concave, and Lorentzian polynomials

1.1

Univariate polynomials

Roots, coefficients, evaluations, interlacing, polar derivatives, and classical one-variable tools.

slides exercises

Analytic Theory of Polynomials — Rahman and Schmeisser, 2002.
Polynomials, roots, and interlacing — Fisk, 2008.

1.2

Multivariate polynomials

Stability, half-plane properties, preservers, and multivariate versions of the one-variable theory.

slides exercises

The Lee–Yang and Pólya–Schur programs I: Linear operators preserving stability — Borcea and Brändén, 2009.
Pólya–Schur master theorems for circular domains and their boundaries — Borcea and Brändén, 2009.
Multivariate stable polynomials: theory and applications — Wagner, 2011.
Polynomials with the half-plane property and matroid theory — Brändén, 2007.
A general Lee–Yang theorem for one-component and multicomponent ferromagnets — Lieb and Sokal, 1981.
A representation theoretic explanation of the Borcea–Brändén characterization — Leake, 2017.

1.3

Applications of stable polynomials

A survey of stable-polynomial methods in graph theory, probability, negative dependence, and interlacing families.

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.

1.4

Beyond stability: log-concave and Lorentzian polynomials

Lorentzian and strongly/completely log-concave polynomials as flexible extensions of stability.

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.
On multivariate Newton-like inequalities — Gurvits, 2009.

1.5

Applications of log-concave polynomials

High-dimensional walks, Mason-type log-concavity, Schur positivity, Potts models, and unimodality phenomena.

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.

2. Polynomial capacity: theory and applications

2.1

Polynomial capacity and Gurvits’ theorem

The capacity functional and the Gurvits inequalities behind permanent and matching-count lower bounds.

slides exercises

2.2

Coefficient bounds

Capacity lower bounds for polynomial coefficients and examples coming from mixed discriminants, mixed volumes, and contingency tables.

slides

On multivariate Newton-like inequalities — Gurvits, 2009.
The Van der Waerden conjecture for mixed discriminants — Gurvits, 2006.
A polynomial time algorithm to approximate the mixed volume within a simply exponential factor — Gurvits, 2007.
Lower bounds for contingency tables via Lorentzian polynomials — Brändén, Leake, and Pak, 2020.

2.3

Coefficient-bounds recap

A second pass through the coefficient-bounds machinery after the holiday break, emphasizing applications and exercises.

slides exercises

Boolean matrices with prescribed row/column sums and stable homogeneous polynomials: combinatorial and algorithmic applications — Gurvits, 2015.
Short survey on stable polynomials, orientations and matchings — Csikvári and Schweitzer, 2020.
Lower bounds for contingency tables via Lorentzian polynomials — Brändén, Leake, and Pak, 2020.

2.4

General capacity bounds for inner products and linear preservers

Capacity bounds arising from linear operators, preservers, and inner-product formulations.

slides exercises

A generalization of permanent inequalities and applications in counting and optimization — Anari and Oveis Gharan, 2017.
Counting matchings via capacity preserving operators — Gurvits and Leake, 2018.
Coefficients and zeros of mixed characteristic polynomials — Zackrisson, 2017.
Polynomials with the half-plane property and matroid theory — Brändén, 2007.

2.5

Applications of the general capacity bounds

Applications to matching counts, matroid optimization, counting, and stable-polynomial relaxations.

slides

Counting matchings via capacity preserving operators — Gurvits and Leake, 2018.
A generalization of permanent inequalities and applications in counting and optimization — Anari and Oveis Gharan, 2017.
Real stable polynomials and matroids: optimization and counting — Straszak and Vishnoi, 2016.
Log-concave polynomials I: Entropy and a deterministic approximation algorithm for counting bases of matroids — Anari, Oveis Gharan, and Vinzant, 2018.

3. Generalizations of capacity

3.1

Capacity and maximum entropy distributions

Capacity viewed through entropy maximization, counting, and continuous maximum-entropy problems.

slides

Entropy, optimization and counting — Singh and Vishnoi, 2015.
On the computability of continuous maximum entropy distributions with applications — Leake and Vishnoi, 2020.
Log-concave polynomials I: Entropy and a deterministic approximation algorithm for counting bases of matroids — Anari, Oveis Gharan, and Vinzant, 2018.
Information theory and statistical mechanics — Jaynes, 1957.
Information theory and statistical mechanics II — Jaynes, 1957.
Maximum entropy Gaussian approximation for the number of integer points and volumes of polytopes — Barvinok and Hartigan, 2009.

3.2

Maximum entropy distributions on unitary orbits

Maximum-entropy and sampling problems over unitary and Lie-group orbits.

slides

A polynomial-time algorithm and applications for matrix sampling from Harish-Chandra–Itzykson–Zuber densities — Leake, McSwiggen, and Vishnoi, 2020.
On the computability of continuous maximum entropy distributions: adjoint orbits of Lie groups — Leake and Vishnoi, 2020.

3.3

Capacity and scaling algorithms

Matrix scaling, operator scaling, tensor scaling, and their links to capacity and optimization.

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, 2017.
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.

3.4

Capacity and invariant theory

Null-cone problems, moment maps, group actions, and non-commutative forms of capacity.

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, Reichenbach, 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.

3.5

Capacity recap

A concluding summary of the different forms of capacity that appeared throughout the course.

slides