Polynomials and (Finite) Free Probability

ACO Seminar
Tuesday, November 3, 2015 - 4:30pm for 1 hour (actually 50 minutes)
Skiles 005
Adam Marcus – Mathematics and PACM, Princeton University
Prasad Tetali
Recent work of the speaker with Dan Spielman and Nikhil Srivastava introduced the ``method of interlacing polynomials'' (MOIP) for solving problems in combinatorial linear algebra. The goal of this talk is to provide insight into the inner workings of the MOIP by introducing a new theory that reveals an intimate connection between the use of polynomials in the manner of the MOIP and free probability, a theory developed by Dan Voiculescu as a tool in the study of von Neumann algebras. I will start with a brief introduction to free probability (for those, like me, who are not operator theorists). In particular, I will discuss the two basic operations in free probability theory (the free additive and free multiplicative convolutions), and how they relate to the asymptotic eigenvalue distributions of random matrices. I will then show how certain binary operations on polynomials act as finite analogues of the free convolutions and how the MOIP is effectively transferring the asymptotic bounds obtained in free probability to bounds in the new theory (which can then be applied to finite scenarios). If time permits, I will show how such a theory gives far better intuition as to how one might apply the MOIP in the future, using recent results on restricted invertibility and the existence of Ramanujan graphs as examples.