Brief Announcement: Almost Universally Optimal Distributed Laplacian Solver

Zusammenfassung

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. First, in the supported version of the CONGEST model, we establish an almost universally optimal Laplacian solver. Namely, we show that any Laplacian system on an n-node graph with shortcut quality SQ (G) can be solved after no(1)SQ(G) log (1/ε) rounds, almost matching our lower bound of Ω∼ (SQ(G)) rounds of any graph G. Our techniques also imply almost universally optimal Laplacian solvers in the full generality of CONGEST, conditional on the efficient construction of shortcuts. In particular, they unconditionally imply a novel Dno(1) log (1/ε) Laplacian solver for excluded-minor graphs with hop-diameter D. Moreover, following a recent line of work in distributed algorithms, we consider a hybrid communication model which enhances CONGEST with limited global power in the form of the node-capacitated clique (NCC) model. In this model, we show the existence of a Laplacian solver with round complexity no(1) log(1/ε). The unifying thread of these results, and our main technical contribution, is the development of nearly-optimal distributed algorithms for a novel congested generalization of the standard part-wise aggregation problem. This primitive accelerates the Laplacian solver of Forster, Goranci, Liu, Peng, Sun, and Ye, and we believe it will find further applications in the future.