[Cs-affiliates] Theory Lunch on Friday

Orecchia, Lorenzo orecchia at bu.edu
Wed Sep 7 11:00:08 EDT 2016


Dear Grads and Instructor,

Welcome back! Our first Theory Lunch of the semester will take place this Friday at 12 noon in MCS 148.  Throughout the semester,  we will meet every Friday from 12pm noon to 1pm in MCS 148 to have lunch, chat and attend an informal talk. If you are interested in Theory Lunch and other happenings in the TCS group, please sign up to the mailing list http://cs-mailman.bu.edu/mailman/listinfo/tcs-announce. All future communications will go through this list.

This week, Sushant Sachdeva will tell us about some more amazing developments in the study of the solution of Laplacian linear systems. See his title, abstract and bio below.

See you on Friday!
Lorenzo

Title: Fast Approximate Gaussian Elimination for Laplacians

Solving systems of linear equations in graph Laplacians is a
fundamental primitive in scientific computing. Starting with the
seminal work of Spielman-Teng that gave the first nearly-linear time
algorithm for solving Laplacian systems, there has been a long line of
work giving faster Laplacian solvers. These solvers have had a large
impact on the design of fast graph algorithms.

In this talk, I'll present a very simple, nearly-linear time Laplacian
solver that is based purely on random sampling, and does not use any
graph theoretic constructions such as low-stretch trees, sparsifiers,
or expanders. Our solver builds a sparse Cholesky factorization for
Laplacians - the symmetric version of Gaussian elimination. More
precisely, it approximates a Laplacian L as U'U, where U is a sparse
upper triangular matrix. Since triangular matrices are easy to invert,
this immediately implies a fast Laplacian solver via iterative
refinement. The analysis is based on concentration of matrix
martingales.

This is joint work with Rasmus Kyng, and will appear at the upcoming FOCS.

About the Speaker:
Sushant Sachdeva is a research scientist at Google. He is interested
in Algorithms, and its connections to optimization, machine learning,
and statistics. His recent research focus has been the design of fast
algorithms for graph problems.
He completed his postdoc at Yale with Dan Spielman (2016), his PhD
from Princeton (2013) under Sanjeev Arora, and his BTech from IIT
Bombay (2008). He is the recipient of Simons Berkeley Research
Fellowship (2013), and the IITB President of India Gold Medal (2008).




-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs-mailman.bu.edu/pipermail/cs-affiliates/attachments/20160907/21048403/attachment.html>


More information about the Cs-affiliates mailing list