Brief Announcement: Almost Universally Optimal Distributed Laplacian Solver
Ioannis Anagnostides, Christoph Lenzen, Bernhard Haeupler, Goran Žužić, Themis Gouleakis · 2022
This paper refines the distributed Laplacian solver recently developed by Forster, Goranci, Liu, Peng, Sun, and Ye (FOCS '21) via the Ghaffari-Haeupler framework (SODA '16) of low-congestion shortcuts. Specifically, if ε > 0 is the error of the Laplacian solver, we obtain two main results.