Talk by Dan Spielman, Yale University

Title:  The Laplacian Matrices of Graphs: Algorithms and Applic ations Host:  Nick Harvey, UBC Computer Science Abstract: The Laplacian matrices of graphs arise in many fields, including Machine Lear ning, Computer Vision, Optimization, Computational Science, and of cou rse Network Analysis.  We will explain what these matrices are and why the y appear in so many applications. We then survey recent ideas that al low us to solve systems of linear equations in Laplacian matrices in nearl y linear time, emphasizing the utility of graph sparsification---the appr oximation of a graph by a sparser one---and a recent algorithm of Kyng andSachdeva that uses random sampling to accelerate Gaussian Elimination. Bio:  Daniel Alan Spielman received his B.A. in Mathematics and Comput er Science from Yale in 1992, and his Ph.D in Applied Mathematics from M. I.T. in 1995. He spent a year as a NSF Mathematical Sciences Postdoc in th e Computer Science Department at U.C. Berkeley, and then taught in the Ap plied Mathematics Department at M.I.T. until 2005.  Since 2006, he has be en a Professor at Yale University.  He is presently the Henry Ford II Prof essor of Computer Science, Statistics and Data Science, Mathematics, an d Applied Mathematics.   He has received many awards, including the 1995 ACM Doctoral Dissertation Award, the 2002 IEEE Information Theory Pa per Award, the 2008 and 2015 Godel Prize, the 2009 Fulkerson Prize, the2010 Nevanlinna Prize, the 2014 Polya Prize, an inaugural Simons Invest igator Award, and a MacArthur Fellowship.  He is a Fellow of the Associat ion for Computing Machinery and a member of the Connecticut Academy of Sci ence and Engineering.  His main research interests include the design and analysis of algorithms, network science, machine learning, digital comm unications and scientific computing.  

---

Find more undergrad events on our internal portal at https://my.cs.ubc.ca.

This event's address: https://my.cs.ubc.ca/event/2017/05/talk-dan-spielman-yale-univ ersity