Item

Abstract

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.