Monday, May 4, 2020

Research Vignette: Geometry of Polynomials

Classical theorems in theoretical computer science typically heavily exploit combinatorial or probabilistic tools. Later on, linear algebraic and geometric tools proved to be fundamental elements in numerous algorithmic or hardness results. In this research vignette, I will explain a new tool known as the “polynomial paradigm,” which can be seen as a bridge between linear algebraic and probabilistic methods; and I will discuss some unexpected applications in computer science.

Given a polynomial $p \in R\lbrack z_{1},\ldots,z_{n}\rbrack$, we can think of it in three ways: (i) coefficients of p, (ii) zeros of p, or (iii) a function that maps n-dimensional complex vectors to complex numbers. Having these three different representations, one can study what happens to one representation when we change another one, or what happens when we apply a mathematical operation such as differentiation, integration, or specialization. For many years, mathematicians studied these questions for many classes of polynomials.

Over the last two decades, a new theme that we call the “polynomial paradigm” emerged. It was observed that if the roots of the (multivariate) polynomial $p$ have a “nice” structure in the n-dimensional complex plane, then one can study the interaction of zeros, coefficients, and function values rigorously. In several pioneering works, Borcea, Brändén, Choe, Liggett, Oxley, Sokal, and Wagner studied the class of real stable polynomials, which can be seen as the right multivariate generalization of real-rooted polynomials. A polynomial $p$ is real stable if it has no root in the upper half of the n-dimensional complex plane. They observed that this class is closed under many operations, such as specialization, differentiation, inversion, etc.

Over the last decade, the polynomial paradigm proved to be a fruitful approach in many areas of science and mathematics. Several applications of this paradigm in theoretical computer science, combinatorics, and linear algebra were discovered, such as improved approximation algorithms for the traveling salesman problem, a purely algebraic proof of the van der Waerden conjecture, and a resolution of the notorious Kadison-Singer conjecture. The general recipe in almost all these applications is as follows: Given a discrete phenomenon, encode it in a complex multivariate polynomial with a nice zero-free region, such as a real stable polynomial. Then study this polynomial via the interplay of coefficients, zeros, and function values. Finally, translate your findings to the domain of the original problem.

In Spring 2019, with Nikhil Srivastava, we organized a semester-long program on Geometry of Polynomials at the Simons Institute, where we invited researchers across several areas of science, mathematics, and computer science to explore this rapidly evolving area. A large group tried to better understand these polynomials and their properties, while many others tried to explore further applications. In the rest of this research vignette, I will explain the journey toward the discovery of a new class of multivariate polynomials that we call completely log-concave polynomials. This discovery and their application motivated several researchers within the program to start collaborating to better understand this class of polynomials and its properties.

Even though the class of real stable polynomials is very powerful, it has its own limitations, and this was apparent to the founders from the beginning. Choe, Oxley, Sokal, and Wagner observed that the support of any homogeneous multi-affine real stable polynomial corresponds to bases of a matroid. On the other hand, Brändén observed that many matroids cannot be realized as the support of any real stable polynomial. A matroid is a combinatorial object that abstracts and generalizes the notion of linear independence in vector spaces. For example, given n vectors $v_{1},\ldots,v_{n}$ they form a linear matroid where any subset $I$ is called an independent set if the corresponding vectors are independent; any maximal independent set of a matroid is called a base. The aforementioned results of Choe et al. show that essentially any discrete phenomenon that we want to encode as a real stable polynomial must come from a matroid in one way or another. The work of Brändén, however, shows that we cannot hope to study problems on matroids through the lens of real stable polynomials.

In search of a new theory
For years I studied applications of real stable polynomials in algorithm design together with my collaborator Nima Anari. For example, in a joint work with Rezaei, we observed that if we have oracle access to coefficients of a real stable polynomial (with non-negative coefficients), we can approximately evaluate it using Markov chains. We had expected that many of our results would be generalizable to all matroids, but it was unclear what the right generalization of real stable polynomials was. In particular, we were looking for a class of polynomials such that bases of any matroid can be realized as a support of a polynomial in this class; and furthermore, similar to real stable polynomials, this class should be closed under many natural operations, such as differentiation and specialization.

Completely log-concave polynomials to the rescue
We crucially observed that in several applications of real stable polynomials, the main underlying property that we exploited was not the structure of the roots; it was rather the log-concavity of the polynomial when considered as a function over the positive orthant. We conjectured that the basis generating polynomial

$$g_{M}(z_{1},\ldots,z_{n}) = \sum_{B\ \text{base}}^{}{}\prod_{i \in B}^{}{}z_{i}\ $$

of any matroid $M$ is log-concave as a function, i.e., $log$ $g_{M}(z_{1},\ldots,z_{n})$ is a concave function over the positive orthant. As a first step, we confirmed our conjecture in simulations. Our next step was to find a tool to study the log-concavity of $g_{M}$. At that point, we had heard about recent exciting developments by Adiprasito, Huh, and Katz on the log-concavity of the coefficients of the characteristic polynomial of any matroid. However, we had no idea if their machinery would be useful to our application. We asked Cynthia Vinzant, at that time a participant in the program on Bridging Continuous and Discrete Optimization at the Simons Institute, and she pointed us to a talk by Huh. That talk turned out to be the key to the proof of the log-concavity of $g_{M}.$ Later on, we started a fruitful collaboration with Vinzant; we proved that the basis generating polynomials of matroids are completely log-concave, i.e., not only is $g_{M}$ log-concave, but any directional derivative of $g_{M}$ along the positive orthant is also log-concave. In this sense, completely log-concave polynomials can be seen as a natural generalization of real stable polynomials that satisfy more or less all closure properties of real stable polynomials. In addition, any matroid can be realized as a support of a completely log-concave polynomial.

Counting bases of matroids
A fundamental question in the theory of computing is whether one can run a Markov chain to sample a uniformly random base of a given matroid. Mihail and U. Vazirani in the 1980s conjectured that this is possible with a simple basis-exchange Markov chain. But for three decades, this conjecture was proved only for a very limited class of matroids known as balanced matroids. When we proved the complete log-concavity of $g_{M}$, the natural next step was to determine if this tool was enough to prove that Mihail and Vazirani’s Markov chain works, i.e., that it mixes rapidly to its stationary distribution. Unfortunately, most of the classical tools to analyze Markov chains are local, and it was unclear how to exploit the complete log-concaveness of basis generating polynomials.

Upon investigating works of Adiprasito et al. and references therein, we observed that one way to study matroids is through the lens of simplicial complexes. A simplicial complex is a downward closed family of sets, and it is well known that independent sets of a matroid form a simplicial complex, also known as an independence complex. On a completely different note, we read several amazing works of Dinur, Kaufman, Mass, and Oppenheim, who studied the mixing time of Markov chains on simplicial complexes. Roughly speaking, they showed that if 1-skeletons of all links of a simplicial complex are very strong expanders, then the Markov chain on maximal faces mixes very rapidly. Naturally, we asked if 1-skeletons of links of the independence complex are very strong expanders. Surprisingly, we observed that this is indeed the case, and this fact is equivalent to $g_{M}$ being completely log-concave. Putting these together, in a joint work with Anari, Liu, and Vinzant, we proved that the basis-exchange Markov chain of Mihail and Vazirani mixes rapidly, proving their 30-year-old conjecture.

After a long journey, we managed to relate three branches of mathematics: (i) Hodge-Riemann relations for combinatorial geometry, (ii) the geometry of polynomials, and (iii) the theory of high-dimensional expanders. We proved that each of these tools can be used to prove the complete log-concavity of the basis generating polynomial of any given matroid. This discovery has already led to many new developments in mathematics, i.e., the use of the machinery of one of these three fields to resolve a problem in another one. Furthermore, the discovery of completely log-concave polynomials has expanded the domain of study within the field of the geometry of polynomials. Over the course of the Simons Institute program on Geometry of Polynomials, several researchers tried to further exploit this new class, studying the underlying “geometry” of these polynomials. I expect to see many more applications of this new class of polynomials as a result of this program.

Research Vignette: Geometry of Polynomials

Related articles

Related stories