Dean Doron: Probabilistic logspace algorithms for Laplacian solvers

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.