Derandomization Beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space

Jack Murtagh, Omer Reingold, Aaron Sidford +1

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 h…