Derandomization Beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space

Understand

We give a deterministic $\tilde{O}(\log n)$-space algorithm for approximately solving linear systems given by Laplacians of undirected graphs, and consequently also approximating hitting times, commute times, and escape probabilities for undirected graphs.

• Previously, such systems were known to be solvable by randomized algorithms using $O(\log n)$ space (Doron, Le Gall, and Ta-Shma, 2017) and hence by deterministic algorithms using $O(\log^{3/2} n)$ space (Saks and Zhou, FOCS 1995 and JCSS 1999).
• Our algorithm combines ideas from time-efficient Laplacian solvers (Spielman and Teng, STOC `04; Peng and Spielman, STOC `14) with ideas used to show that Undirected S-T Connectivity is in deterministic logspace (Reingold, STOC `05 and JACM `08; Rozenman and Vadhan, RANDOM `05).