Almost Universally Optimal Distributed Laplacian Solvers via Low-Congestion Shortcuts

<p> In this paper, we refine the (almost) <em>existentially optimal</em> distributed Laplacian solver of Forster, Goranci, Liu, Peng, Sun, and Ye (FOCS ‘21) into an (almost) <em>universally optimal</em> distributed Laplacian solver. Specifically, when the topology is known (i.e., the Supported-CONGEST model), we show that any Laplacian system on an <em>n</em>-node graph with <em>shortcut quality</em> 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 <em>G</em> 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 <em>D</em> 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-<em>congested</em> generalization of the standard <em>part-wise aggregation</em> problem, which could be of independent interest. </p>