Dean Doron: Probabilistic logspace algorithms for Laplacian solvers

Tuesday, December 11, 2018 - 4:00pm to 5:00pm
Light Refreshments at 3:45pm
Patil/Kiva G449
Dean Doron, UT Austin
Abstract:  A series of breakthroughs initiated by Spielman and Teng culminated in the construction of nearly linear time Laplacian solvers, approximating the solution of a linear system Lx = b, where L is the Laplacian of an undirected graph. 
In this talk we study the space complexity of the problem. We show a probabilistic, logspace algorithm solving the problem. We further extend the algorithm to other families of graphs like Eulerian graphs and graphs that mix in polynomial time.
We also shortly discuss complexity-theoretic motivations for studying linear-algebraic problems in small space, and relations to local algorithms.
Based on joint work with François Le Gall and Amnon Ta-Shma.