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.
Streetchange won a Webby award for Best Use of Machine Learning on the Web! Congratulations to the team. Streetchange is a new way of measuring changes in the physical appearances of neighborhoods using a computer vision algorithm. The researchers calculated Streetchange by algorithmically comparing Google Street View images of the same location captured in different… Continue reading →
Stephen Hawking passed away yesterday. He was 76. He visited the Black Hole Initiative in 2016 (pictured above). In 2006, Prof. Shing-Tung Yau helped arrange Prof. Hawking’s visit to China, where he has remained a popular cultural figure. In the words of Prof. Yau, “He was very friendly and was willing to explain physics to laymen…. Continue reading →