@online{Anagnostides_2109.05151,
TITLE = {Almost Universally Optimal Distributed {L}aplacian Solvers via Low-Congestion Shortcuts},
AUTHOR = {Anagnostides, Ioannis and Lenzen, Christoph and Haeupler, Bernhard and Zuzic, Goran and Gouleakis, Themis},
LANGUAGE = {eng},
URL = {https://arxiv.org/abs/2109.05151},
EPRINT = {2109.05151},
EPRINTTYPE = {arXiv},
YEAR = {2021},
ABSTRACT = {In this work we refine the analysis of the distributed Laplacian solver<br>recently established by Forster, Goranci, Liu, Peng, Sun, and Ye (FOCS '21),<br>via the Ghaffari-Haeupler framework (SODA '16) of low-congestion shortcuts.<br>Specifically, if $\epsilon > 0$ represents the error of the solver, we derive<br>two main results. First, for any $n$-node graph $G$ with hop-diameter $D$ and<br>treewidth bounded by $k$, we show the existence of a Laplacian solver with<br>round complexity $O(n^{o(1)}kD \log(1/\epsilon))$ in the CONGEST model. For<br>graphs with bounded treewidth this circumvents the notorious $\Omega(\sqrt{n})$<br>lower bound for "global" problems in general graphs. Moreover, following a<br>recent line of work in distributed algorithms, we consider a hybrid<br>communication model which enhances CONGEST with very limited global power in<br>the form of the recently introduced node-capacitated clique. In this model, we<br>show the existence of a Laplacian solver with round complexity $O(n^{o(1)}<br>\log(1/\epsilon))$. The unifying thread of these results is an application of<br>accelerated distributed algorithms for a congested variant of the standard<br>part-wise aggregation problem that we introduce. This primitive constitutes the<br>primary building block for simulating "local" operations on low-congestion<br>minors, and we believe that this framework could be more generally applicable.<br>},
}