Introduction to real-rooted polynomials, Newton's inequalities, interlacing, the matching polynomial and the Heilman-Lieb theorem.
Tuesday, January 22nd, 2019
11:15 am–12:35 pm
Speaker: Shayan Oveis Gharan (University of Washington)
I will talk about real stable polynomials as a "natural" generalization of (univariate) real rooted polynomials, and their corresponding probability distributions known as strongly Rayleigh distributions.
I will then talk about stability preserver operators which are natural tools to prove a given polynomial is real stable.
We will see many applications of these polynomials and preserver operators in computer science. In particular, I will talk about a deterministic algorithm to approximate permanent of matrices with nonnegative entries, approximation algorithms for traveling salesman problems, and repulsive point processes, a.k.a., DPPs.
2:00 pm–3:20 pm
Speaker: Jan Vondrák (Stanford University)
Overview of non-constructive methods: probabilistic / topological / algebraic, some classical applications. Introduction to the method of interlacing polynomials and Ramanujan graphs.
3:45 pm–5:05 pm
Speaker: Nikhil Srivastava (UC Berkeley)
In the first lecture, I will prove the real rootedness of a large class of expected characteristic polynomials, completing Jan's proof of the existence of Ramanujan graphs. I will then explain two univariate techniques for bounding zeros of expected characteristic polynomials: the first is from algebraic combinatorics and the second is related to free probability theory.
In the second lecture, I will explain the proof of Weaver's conjecture, a question in discrepancy theory which is known to imply a solution of the Kadison-Singer problem. The key ingredient is a multivariate technique for controlling the roots of expected characteristic polynomials. I will conclude by describing connections to other research areas represented in this program, as well as some open questions.
Wednesday, January 23rd, 2019
9:30 am–10:50 am
Speaker: Nikhil Srivastava (UC Berkeley)
In the first lecture, I will prove the real rootedness of a large class of expected characteristic polynomials, completing Jan's proof of the existence of Ramanujan graphs. I will then explain two univariate techniques for bounding zeros of expected characteristic polynomials: the first is from algebraic combinatorics and the second is related to free probability theory.
In the second lecture, I will explain the proof of Weaver's conjecture, a question in discrepancy theory which is known to imply a solution of the Kadison-Singer problem. The key ingredient is a multivariate technique for controlling the roots of expected characteristic polynomials. I will conclude by describing connections to other research areas represented in this program, as well as some open questions.
11:15 am–12:35 pm
Speaker: Shayan Oveis Gharan (University of Washington)
I will talk about real stable polynomials as a "natural" generalization of (univariate) real rooted polynomials, and their corresponding probability distributions known as strongly Rayleigh distributions.
I will then talk about stability preserver operators which are natural tools to prove a given polynomial is real stable.
We will see many applications of these polynomials and preserver operators in computer science. In particular, I will talk about a deterministic algorithm to approximate permanent of matrices with nonnegative entries, approximation algorithms for traveling salesman problems, and repulsive point processes, a.k.a., DPPs.
2:00 pm–3:20 pm
Speaker: Michel Goemans (Massachusetts Institute of Technology)
In these two talks, I will introduce hyperbolic optimization, a class of convex optimization problems derived from hyperbolic polynomials. I will discuss special cases, properties, ways of obtaining hyperbolic polynomials/cones, and other topics.
3:45 pm–5:05 pm
Speaker: Michel Goemans (Massachusetts Institute of Technology)
In these two talks, I will introduce hyperbolic optimization, a class of convex optimization problems derived from hyperbolic polynomials. I will discuss special cases, properties, ways of obtaining hyperbolic polynomials/cones, and other topics.
Thursday, January 24th, 2019
9:30 am–10:50 am
Speaker: Rainer Sinn (Freie Universität Berlin)
The two talks are an introduction to the point of view of real algebraic geometry on hyperbolic polynomials. Central themes are 1) how to test if a given real polynomial is hyperbolic; 2) real root counting and sums of squares of matrix polynomials; and 3) determinantal representations and the generalized Lax conjecture.
11:15 am–12:35 pm
Speaker: Rainer Sinn (Freie Universität Berlin)
The two talks are an introduction to the point of view of real algebraic geometry on hyperbolic polynomials. Central themes are 1) how to test if a given real polynomial is hyperbolic; 2) real root counting and sums of squares of matrix polynomials; and 3) determinantal representations and the generalized Lax conjecture.
2:00 pm–3:20 pm
Speaker: Alistair Sinclair (UC Berkeley)
Partition functions are a class of combinatorially derived polynomials that have many applications in statistical physics, combinatorics and machine learning. For almost all interesting partition functions exact evaluation is computationally intractable, so interest is focused on efficient approximation. The computational complexity of such approximation is often intimately related to the existence of phase transitions in the underlying physical system described by the partition function, which in turn are related to its analyticity properties. In these talks I will briefly discuss three widely applicable algorithmic techniques—Markov chain Monte Carlo, correlation decay, and polynomial interpolation—and how they relate to phase transitions, using the classical Ising model as a running example.
3:45 pm–5:05 pm
Speaker: Alistair Sinclair (UC Berkeley)
Partition functions are a class of combinatorially derived polynomials that have many applications in statistical physics, combinatorics and machine learning. For almost all interesting partition functions exact evaluation is computationally intractable, so interest is focused on efficient approximation. The computational complexity of such approximation is often intimately related to the existence of phase transitions in the underlying physical system described by the partition function, which in turn are related to its analyticity properties. In these talks I will briefly discuss three widely applicable algorithmic techniques—Markov chain Monte Carlo, correlation decay, and polynomial interpolation—and how they relate to phase transitions, using the classical Ising model as a running example.
Friday, January 25th, 2019
9:30 am–10:50 am
Speaker: Alexander Barvinok (University of Michigan)
By a "partition function" we understand a combinatorially defined polynomial, often multivariate and with many monomials, such as the permanent of a matrix. Under typical circumstances, it is not feasible to write it explicitly as a sum of monomials (because there are too many of them), although for every given monomial, some simple combinatorial rule quickly tells us whether it enters the polynomial and with what coefficient. We are interested in computing (approximating) such a polynomial efficiently at a given point. I will discuss an approach which allows one to do it, provided there are no complex zeros of the partition function in the vicinity of the point of interest. Examples include the already mentioned permanent, its higher-dimensional extensions, the matching polynomial of graphs and hypergraphs, the graph homomorphism and chromatic polynomial, as well as polynomials enumerating 0-1 solutions to sparse systems of linear equations. We will compare and contrast the approach with the Lee-Yang theory of phase transition in statistical physics and discuss its challenges.
11:15 am–12:35 pm
Speaker: Alexander Barvinok (University of Michigan)
By a "partition function" we understand a combinatorially defined polynomial, often multivariate and with many monomials, such as the permanent of a matrix. Under typical circumstances, it is not feasible to write it explicitly as a sum of monomials (because there are too many of them), although for every given monomial, some simple combinatorial rule quickly tells us whether it enters the polynomial and with what coefficient. We are interested in computing (approximating) such a polynomial efficiently at a given point. I will discuss an approach which allows one to do it, provided there are no complex zeros of the partition function in the vicinity of the point of interest. Examples include the already mentioned permanent, its higher-dimensional extensions, the matching polynomial of graphs and hypergraphs, the graph homomorphism and chromatic polynomial, as well as polynomials enumerating 0-1 solutions to sparse systems of linear equations. We will compare and contrast the approach with the Lee-Yang theory of phase transition in statistical physics and discuss its challenges.
2:00 pm–3:20 pm
Speaker: Nima Anari (Stanford University)
This tutorial will focus on a generalization of real stable generating polynomials called complete log-concave polynomials. In this generalization, the strict requirements on the locations of roots are dropped and replaced instead by the weaker property of log-concavity (as a function) over the positive orthant.
Complete log-concavity captures a large class of distributions and their associated generating polynomials, which includes uniform measures over the bases or independent sets of matroids, volumes of Minkowski sums, the random cluster model in the ``negative dependence’' regime, and certain powers of determinantal point processes.
We will survey methods to verify complete log-concavity as well as operations that preserve it. We will see some applications of complete log-concavity, including a proof of Mason’s ultra-log-concavity conjecture on the number of independent sets in matroids.
