From the Inside: Geometry of Polynomials

by Mohan Ravichandran (Mimar Sinan University)

The Spring 2019 Simons Institute program on Geometry of Polynomials was an initiative that attempted to develop and consolidate the eponymous area of research, a new discipline at the intersection of combinatorics, discrete probability, and theoretical computer science. Over the past fifteen years, several breakthrough results had suggested new, unexpected connections between discrete combinatorial structures and natural associated polynomials, and had sparked a steady growth of interest in exploring these more thoroughly. 

There are several natural ways of looking at a polynomial: looking at it as a function, examining its coefficients, and analyzing its roots. There are other perspectives, such as analyzing associated algebras, but the geometry of polynomials is distinguished by this triangle of function-coefficients-roots perspectives. There is a natural class of polynomials, namely hyperbolic polynomials, where this interaction plays out most fruitfully: as functions, they are log concave on natural domains, their coefficients have useful discrete concavity properties, and their roots avoid special regions in Euclidean space.

In 2006, Leonid Gurvits used hyperbolic polynomials to give a striking new proof of the well-known van der Waerden conjecture. Around the same time, several researchers, notably Petter Brändén and Julius Borcea, developed the theory of these polynomials. Among other things, they resolved problems that go back to Pólya and Schur on characterizing linear operators that preserve hyperbolicity. In 2013, Adam Marcus, Daniel Spielman, and Nikhil Srivastava developed a quantitative version of the Borcea-Brändén theory to resolve the Kadison-Singer problem, a famous problem arising from the mathematical foundations of quantum mechanics that seemingly had nothing to do with polynomials. 

As is common in a young, developing, and many-headed area, a neat summary is difficult, and indeed organizing these results into a coherent narrative was one of the goals of the Geometry of Polynomials research program. Some common themes can nevertheless be identified. 

1. Going beyond hyperbolic polynomials. Gurvits had proposed a larger class, which he called “strongly log-concave polynomials,” as a candidate in 2008. Over the past year, Nima Anari, Shayan Oveis Gharan, Kuikui Liu, and Cynthia Vinzant, as well as, independently, Brändén and June Huh, developed a beautiful theory of these polynomials, building upon recent work by Karim Adiprasito, Eric Katz, and Huh, in which they developed a combinatorial version of classical Hodge theory. Consequences include the resolution of decades-old combinatorial questions concerning matroids.

2. Exploiting zero-free regions for approximate counting. Approximately evaluating partition functions of statistical physics models is a basic problem in theoretical computer science, and while this is usually done using Markov chain Monte Carlo methods, the past few years have seen powerful deterministic algorithms for the same problem. Alexander Barvinok has shown the close connection between approximate counting and the presence of zero-free regions of these partition functions (many of which are polynomials), but the precise nature of this connection is still to be fleshed out.

3. Developing connections to continuous optimization. A theory of continuous optimization based on hyperbolic polynomials has been developed by several authors, notably Jim Renegar, and understanding the precise relation between hyperbolic programming and the more traditional semidefinite programming is a major and challenging problem. 

One striking feature of the Geometry of Polynomials program was the presence of these three distinct groups of researchers, and the three workshops during the program reflected this. Each workshop, however, also strove to showcase the connections among these three areas. Apart from these workshops, two important components of the program were a session each week where a different researcher would propose open problems, and a weekly seminar where participants would present current research. 

Among the highlights of the program were two daylong open-problem sessions, one each after the first two workshops. They were modeled upon workshops conducted at the American Institute of Mathematics: over the course of a day, participants would present open problems, which would be voted on, after which people would work in groups on the three or four that received the most votes. Both sessions led to fruitful collaborations among unacquainted researchers, many of whom are currently working together to complete initiated projects. Facilitating this collaboration was also the brilliant design of the Simons Institute, with its large common areas filled with boards for collaborative research. 

Let me mention here a couple of fascinating developments that occurred during the program. Will Perkins and Sarah Cannon, both participants in the program, spent time developing a theory that shows that for several statistical physics partition functions, there are fast deterministic algorithms in the very regime where randomized algorithms are slow. And strikingly, they showed that the deterministic algorithms, which build upon ideas of Barvinok, are fast for the same reason the randomized algorithms are slow! In another direction, there was major progress on the elegant log-concave polynomials–based randomized algorithms for counting bases of matroids due to Anari, Oveis Gharan, Liu, and Vinzant. The first three of them, all program participants, and, independently, Heng Guo (also a program participant), Mary Cryan, and Giorgos Mousa showed that the running time of this algorithm essentially equals that of far more specialized algorithms for the special case of counting spanning trees in a graph. 

It was a privilege to be a participant in this Simons Institute program, which laid the foundations for a new interdisciplinary area of research. The program also laid the foundations for interactions with other areas, such as polyhedral combinatorics, tropical geometry, and the theory of high-dimensional expanders. There are surely many more surprising connections waiting to be discovered, and it is fortunate that the Simons Institute facilitated the coming together of disparate researchers for collaboration, and helped in the forming of a community well poised to make these discoveries.

Related Articles

Related stories

,