Accelerated Distributed Laplacian Solvers via Shortcuts


الملخص بالإنكليزية

In this work we refine the analysis of the distributed Laplacian solver recently established by Forster, Goranci, Liu, Peng, Sun, and Ye (FOCS 21), via the Ghaffari-Haeupler framework (SODA 16) of low-congestion shortcuts. Specifically, if $epsilon > 0$ represents the error of the solver, we derive two main results. First, for any $n$-node graph $G$ with hop-diameter $D$ and treewidth bounded by $k$, we show the existence of a Laplacian solver with round complexity $O(n^{o(1)}kD log(1/epsilon))$ in the CONGEST model. For graphs with bounded treewidth this circumvents the notorious $Omega(sqrt{n})$ lower bound for global problems in general graphs. Moreover, following a recent line of work in distributed algorithms, we consider a hybrid communication model which enhances CONGEST with very limited global power in the form of the recently introduced node-capacitated clique. In this model, we show the existence of a Laplacian solver with round complexity $O(n^{o(1)} log(1/epsilon))$. The unifying thread of these results is an application of accelerated distributed algorithms for a congested variant of the standard part-wise aggregation problem that we introduce. This primitive constitutes the primary building block for simulating local operations on low-congestion minors, and we believe that this framework could be more generally applicable.

تحميل البحث