English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In this paper, we refine the (almost) \emph{existentially optimal}distributed Laplacian solver recently developed by Forster, Goranci, Liu, Peng,Sun, and Ye (FOCS `21) into an (almost) \emph{universally optimal} distributedLaplacian solver.  Specifically, when the topology is known, we show that any Laplacian systemon an $n$-node graph with \emph{shortcut quality} $\text{SQ}(G)$ can be solvedwithin $n^{o(1)} \text{SQ}(G) \log(1/\varepsilon)$ rounds, where $\varepsilon$is the required accuracy. This almost matches our lower bound which guaranteesthat any correct algorithm on $G$ requires $\widetilde{\Omega}(\text{SQ}(G))$rounds, even for a crude solution with $\varepsilon \le 1/2$. Even in theunknown-topology case (i.e., standard CONGEST), the same bounds also hold inmost networks of interest. Furthermore, conditional on conjectured improvementsin state-of-the-art constructions of low-congestion shortcuts, the CONGESTresults will match the known-topology ones.  Moreover, following a recent line of work in distributed algorithms, weconsider a hybrid communication model which enhances CONGEST with limitedglobal power in the form of the node-capacitated clique (NCC) model. In thismodel, we show the existence of a Laplacian solver with round complexity$n^{o(1)} \log(1/\varepsilon)$.  The unifying thread of these results, and our main technical contribution, isthe study of novel \emph{congested} generalization of the standard\emph{part-wise aggregation} problem. We develop near-optimal algorithms forthis primitive in the Supported-CONGEST model, almost-optimal algorithms in(standard) CONGEST, as well as a very simple algorithm for bounded-treewidthgraphs with slightly worse bounds. This primitive can be readily used toaccelerate the FOCS`21 Laplacian solver. We believe this primitive will findfurther independent applications.

Almost Universally Optimal Distributed Laplacian Solvers via Low-Congestion Shortcuts