The Laplacian Paradigm in Deterministic Congested Clique

Abstract

In this paper, we bring the techniques of the Laplacian paradigm to the congested clique, while further restricting ourselves to deterministic algorithms. In particular, we show how to solve a Laplacian system up to precision $\epsilon$ in $n^{o(1)}\log (1/\epsilon )$ rounds. We show how to leverage this result within existing interior point methods for solving flow problems. We obtain an $m^{3/7+o(1)}{U}^{1/7}$ round algorithm for maximum flow on a weighted directed graph with maximum weight $U$, and we obtain an $\tilde{O}(m^{3/7}(n^{0.158}+n^{o(1)}\text{poly}\log W))$ round algorithm for unit capacity minimum cost flow on a directed graph with maximum cost $W$. Hereto, we give a novel routine for computing Eulerian orientations in $O(\log n{\log }^{\ast }n)$ rounds, which we believe may be of separate interest.

arXiv commentTo be presented at the 42nd ACM Symposium on Principles of Distributed Computing (PODC 2023) as brief announcement