Polynomial Capacity: Theory, Applications, Generalizations

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

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 Polynomials
    1. Univariate polynomials [slides, exercises]
    2. Multivariate polynomials [slides, exercises]
    3. Applications of stable polynomials (without polynomial capacity) [slides]
    4. Beyond stability: log-concave and Lorentzian polynomials [slides, exercises]
    5. Applications of log-concave polynomials [slides, exercises]
  2. Polynomial Capacity: Theory and Applications
    1. Polynomial capacity and Gurvits' theorem [slides, exercises]
    2. Coefficient bounds [slides]
    3. Coefficient bounds recap (after holiday break) [slides, exercises]
    4. General capacity bounds for inner products and linear preservers [slides, exercises]
    5. Applications of the general capacity bounds [slides]
  3. Generalizations of Capacity
    1. Capacity and maximum entropy distributions [slides]
    2. Maximum entropy distributions on unitary orbits [slides]
    3. Capacity and scaling algorithms [slides]
    4. Capacity and invariant theory [slides]
    5. Capacity recap: All the forms of capacity [slides]