Dan Spielman (Yale University) discusses expander graphs, laplacians matrices, and his CMSA public talk as part of the Special Program on Combinatorics and Complexity.
Title: The Laplacian Matrices of Graphs: Algorithms and Applications
Abstract: The Laplacian matrices of graphs arise in many fields, including Machine Learning, Computer Vision, Optimization, Computational Science, and of course Network Analysis. We will explain what these matrices are and why they appear in so many applications.
We then survey recent ideas that allow us to solve systems of linear equations in Laplacian matrices in nearly linear time, emphasizing the utility of graph sparsification—the approximation of a graph by a sparser one—and a recent algorithm of Kyng and Sachdeva that uses random sampling to accelerate Gaussian Elimination.
The main focus of the workshop is the application of algebraic method to study problems in combinatorics. In recent years there has been a large number of results in which the use of algebraic technique has resulted in significant improvements to long standing open problems. Such problems include the finite field Kakeya problem, the distinct distance problem of Erdos and, more recently, the cap-set problem. The workshop will include talks on all of the above mentioned problem as well as on recent development in related areas combining combinatorics and algebra.
The following playlist contains videos from the workshop: