CMI Seminar

A multivariate polynomial over the complex numbers is said to be stable with respect to a region H if it does not vanish when its arguments lie in H. An important special case is when H is the product of unit disks in the complex plane (a "polydisk"), in which case stability with H is equivalent to the statement that the polynomial is non-zero when all its arguments lie in the unit disk. Another important case is when H is the product of upper half planes, in which case stability w.r.t H is equivalent to the statement that the polynomial is non-zero when all its arguments have positive imaginary parts.
    While the term "stability" itself originated in control theory, stable polynomials and their properties have had several applications in fields as diverse as linear algebra, combinatorics and probability theory, and computational complexity theory, among others. In these two talks, I will attempt to discuss the following three applications:
    1) #P-hardness of computing the magnetization of the Ising model.
    This requires an extension to the Lee-Yang theorem -- a stability theorem w.r.t the unit disk for the partition function of the Ising model that was itself proven in order to study phase transitions.
    2) Exact characterization of probabilities for which the Lovász local lemma is valid.
    This uses a statement about the stability of the independent set polynomial w.r.t a polydisk. We will discuss a related question regarding the effective verification of stability properties and its possible implications for a different proof of the Lee-Yang theorem.
    3) Negative association for probability distributions on spanning trees.
    Here, one uses the stability of the generating function of the given probability distribution w.r.t to the upper half plane (also known as the "strongly Raleigh" property in this context). This connection was used in a breakthrough result of Oveis-Gharan, Saberi and Singh [O-GSS11] on approximate solutions to the Traveling Salesperson Problem.