Talk by Dan Spielman, Yale University
Date
–
Location
Hugh Dempster Pavilion - Room 110, 6245 Agronomy Rd.
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