Lecture: The path from Laplacian matrices to the Kadison-Singer problem

Daniel Spielman

Abstract:

Linear algebra in computer science and mathematics:
The path from Laplacian matrices to the Kadison-Singer problem.
I will tell the story of some remarkable interactions between Mathematics and Computer Science, showing how progress in each area built on developments in the other.
The main plot line begins with my work on designing algorithms for solving systems of linear equations in the Laplacian matrices of graphs and ends with the solution of the Kadison-Singer problem. Along the way we will encounter mathematical results in combinatorics, random matrix theory, and the geometry of polynomials. These were inspired by other algorithmic problems, such as those of estimating the volumes and mixed volumes of convex bodies, of estimating the permanents and mixed discriminants of matrices, of computing partition functions of mathematical physics, and of accelerating algorithms by subsampling their inputs.

---