Search Mailing List Archives

Limit search to: Subject & Body Subject Author
Sort by: Reverse Sort
Limit to: All This Week Last Week This Month Last Month
Select Date Range     through    

[theory-seminar] Fwd: TCS+ (new season): a group at Stanford?

Mary Wootters marykw at
Mon Sep 12 16:42:31 PDT 2016

Hi all,

See the announcement below from Gautam Kamath: TCS+ is back up and running
for the academic year, and the first talk is this Wednesday, by Sushant
Sachdeva!  (And bi-weekly thereafter).

G also asks in his email if there are any students who are interested in
organizing regular TCS+ viewings at Stanford.  We had these when I was a
grad student at UMich, and it was a great way to consume the talks.  You
actually get to interact (a little bit) with the speakers, and more
importantly, I found that I actually watched the talks if I was doing it
with others.  (Somehow when I decide I'll watch later on my own, it doesn't
always end up happening...)  If you're interested, let me and G know.  I
can rustle up some money for donuts or something if that'll help :)


---------- Forwarded message ----------
From: Gautam "G" Kamath <g at>
Date: Mon, Sep 12, 2016 at 10:49 AM
Subject: TCS+ (new season): a group at Stanford?
To: marykw at

Hi Mary,

    As you might have heard, we're starting up the next semester of TCS+.
    The talk will given by Sushant Sachdeva, this Wednesday 1pm EST
    (as usual). The announcement is at the bottom of this email. Would
    you mind sending this announcement to any relevant lists at Stanford?

    Also, we're always trying to reach out and getting small groups to form
    join the talks live - I think it makes the experience better for

    Do you know if there is a student or postdoc at Stanford University
    who would be interested in organizing group viewings of TCS+ on a
    regular basis? If so they could serve as a "point of contact" for us.

    No obligation of course, but if you could help reach out at the
    start of the semester it would be great! (Of course I also
    understand there are other scheduling constraints, and students may
    have other events on their mind...)


    PS: We're also on the lookout for great speakers & results! Feel
    free to suggest any, e.g. by using the online form
<>) or by email.


We're excited to start a new year of TCS+ talks! Our first talk this Fall
will take place this coming Wednesday, September 14th at 1:00 PM Eastern
Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). We're
honored to have Sushant Sachdeva from Google as our first speaker. Sushant
will talk about beautiful work with Kyng, to appear in the upcoming FOCS,
giving an elegant algorithm for "Fast Approximate Gaussian Elimination for
Laplacians" (abstract below).

We'll continue following the same procedure as in previous years: for
groups, please sign up on the online form at
plustcs/livetalk/live-seat-reservation, and we'll email you a link to the
hangout the evening prior to the talk.

Please see our website for more
information. The following talk will be on Sept. 28th, with Swastik
Kopparty from Rutgers as speaker.

Hoping to see you all there,

The organizers

Speaker: Sushant Sachdeva (Google)
Title: Fast Approximate Gaussian Elimination for Laplacians

Abstract: 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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the theory-seminar mailing list