# Almost Universally Optimal Distributed Laplacian Solvers via Low-Congestion Shortcuts

In this paper, we refine the (almost) *existentially optimal* distributed Laplacian solver of Forster, Goranci, Liu, Peng, Sun, and Ye (FOCS ‘21) into an (almost) *universally optimal* distributed Laplacian solver. Specifically, when the topology is known (i.e., the Supported-CONGEST model), we show that any Laplacian system on an *n*-node graph with *shortcut quality* SQ(G) can be solved after n ° (1)SQ(G)log(1/€) rounds, where €>0 is the required accuracy. This almost matches our lower bound that guarantees that any correct algorithm on *G* requires Ω~(SQ(G)) rounds, even for a crude solution with € ≤1/2. Several important implications hold in the unknown-topology (i.e., standard CONGEST) case: for excluded-minor graphs we get an almost universally optimal algorithm that terminates in D⋅n ° (1)log(1/€) rounds, where *D* is the hop-diameter of the network; as well as n ° (1)log(1/€)-round algorithms for the case of SQ(G)≤n ° (1), which holds for most networks of interest. 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 model. In this model, we show the existence of a Laplacian solver with round complexity n ° (1)log(1/€). The unifying thread of these results, and our main technical contribution, is the development of near-optimal algorithms for a novel p-*congested* generalization of the standard *part-wise aggregation* problem, which could be of independent interest.

## History

## Primary Research Area

- Algorithmic Foundations and Cryptography

## Journal

Distributed Computing## Publisher

Springer Nature## Open Access Type

- Green

## Sub Type

- Article