FOCS 2013 Workshop on Zeros of Polynomials
and their Applications to Theory

Problems in many different areas of mathematics reduce to questions about the zeros of complex univariate and multivariate polynomials. Recently, several significant and seemingly unrelated results relevant to theoretical computer science have benefited from taking this route: they rely on showing, at some level, that a certain univariate or multivariate polynomial has no zeros in a region. This is achieved by inductively constructing the relevant polynomial via a sequence of operations which "preserve" the property of not having roots in the required region. The goal of this workshop is to present this viewpoint and to convey why the study of zeros is a natural, powerful, and versatile tool. The first two talks are meant to be "tutorials" and introduce the relevant tools and techniques from this area. The subsequent three talks build up on these techniques and demonstrate applications to the Traveling Salesman Problem, the Kadison-Singer problem, and phase transitions and computational complexity of problems in statistical physics.

Time	Speaker	Title and Abstract
9:50-10:50	Nisheeth Vishnoi (Microsoft Research, India)	Tutorial I: An Introduction to Stability and Strongly Rayleigh Measures
11:00-12:00	Adam Marcus (Yale)	Tutorial II: Hyperbolicity and Interlacing
12:00-2:00	Lunch break (on your own)
2:00-3:00	Shayan Oveis-Gharan (Stanford/UC Berkeley)	The Traveling Salesman Problem and Strongly Rayleigh Measures
3:00-3:20	Break
3:20-4:20	Daniel Spielman (Yale)	The Solution of the Kadison-Singer Problem.
4:30-5:30	Piyush Srivastava (UC Berkeley)	Phase Transitions, Zeros of Polynomials and the Computational Complexity of Problems in Statistical Physics

Speaker: Nisheeth Vishnoi (Microsoft Research, India)
Title: Tutorial I: An Introduction to Stability and Strongly Rayleigh Measures
Abstract: This talk is meant to be a gentle introduction to the stability of polynomials and the remarkable closure properties they satisfy. Subsequently, it will be shown how one can use these closure properties to derive interesting properties, such as negative correlation, for probability distributions whose generating polynomials are “real-stable”. Such probability distributions are known as “Strongly Rayleigh” measures and are useful in TCS applications since they satisfy the strongest form of negative dependence.
A writeup is available here: http://research.microsoft.com/en-us/um/people/nvishno/Site/Publications_files/ZerosIntro.pdf

Speaker: Adam Marcus (Yale)
Title: Tutorial II: Hyperbolicity and Interlacing
Abstract: This talk will build on the previous talk and introduce certain inequalities and areas where real stable polynomials have been used in TCS. Of particular emphasis will be the connection between real stable polynomials and hyperbolic polynomials, Gurvits’ proof of the lower bound of the permanent, and the role real stability plays in proving that a family of polynomials is interlacing.

Speaker: Shayan Oveis-Gharan (Stanford/UC Berkeley)
Title:The Traveling Salesman Problem and Strongly Rayleigh Measures
Abstract:I describe a randomized rounding algorithm for the following problem: given a fractional solution x of the subtour elimination polytope (a.k.a. Held-Karp relaxation of TSP) such that for an absolute constant delta any cut (S,V-S) that is not a degree cut has value at least 2+delta in x. Write (3/2-eps)x as a convex combination of integral TSP tours where eps is a function of delta.
Our algorithm first samples a random spanning tree from a maximum entropy distribution defined by the vector x and then makes it Eulerian by adding the minimum cost matching on the odd degree vertices of the tree. To analyze our algorithm I will use the fact that the distribution of random spanning trees belongs to a more general class of measures called Strongly Rayleigh. These are probability distribution whose corresponding generating function is a real stable polynomial. This means that strongly Rayleigh measures are closed under projection, truncation and they satisfy strongest forms of negative dependence.
Based on a joint work with Amin Saberi and Mohit Singh.
Paper available here: http://www.stanford.edu/~shayan/Publications_files/tsp.pdf

Speaker: Daniel Spielman (Yale)
Title: The Solution of the Kadison-Singer Problem.
Abstract: In 1959, Kadison and Singer posed a problem in mathematical physics that has been shown to be equivalent to problems in many domains. In this lecture, we will explain its connections to discrepancy theory and the paving conjectures. We will then explain how we use the theory of real stable polynomials to solve these conjectures.
Our main technical result is an upper bound on the largest root of the expected characteristic polynomial of a sum of random symmetric rank-1 matrices. We use this bound to prove that there exists a balanced partition of certain sets of vectors. This result can be viewed as a strengthening of the "matrix Chernoff bounds" of Ahlswede and Winter, Rudelson and Vershynin, and Tropp.
This is joint work with Adam Marcus and Nikhil Srivastava.
Paper available here: http://arxiv.org/pdf/1306.3969v2.pdf

Speaker: Piyush Srivastava (UC Berkeley)
Title:Phase Transitions, Zeros of Polynomials and the Computational Complexity of Problems in Statistical Physics
Abstract: The study of zeros of polynomials took hold in statistical physics through the seminal work of Lee and Yang [1952], who related phase transitions in the Ising model (a classical statistical model for magnetism) to the location of zeros of a certain class of combinatorial polynomials (known as "partition functions"). In order to use this connection, they then proved a striking stability result for this class of polynomials: in particular, they showed that the partition function of the so-called "ferromagnetic" Ising model is stable with respect to the unit disk in the complex plane.
In this talk, we will briefly survey the Lee-Yang theorem and its connection to phase transitions. We will then present our recent extension of the Lee-Yang theorem which has applications to proving the #P-hardness of computing the magnetization of the Ising model. We will also present another example of this method of using stability results to prove #P-hardness by applying a theorem of Heilmann and Lieb on the stability of the matching polynomial to prove the #P-hardness of computing the average size of a matching.
This is based on joint work with Alistair Sinclair.
Paper available here: http://arxiv.org/pdf/1211.2376v2.pdf
A write up on the Lee-Yang theory of Phase transitions is available here: https://www.cs.berkeley.edu/~piyushsr/docs/phase.pdf