The Laplacian Paradigm in the Broadcast Congested Clique
Sebastian Forster, Tijn de Vos · 2022
In this paper, we bring the main tools of the Laplacian paradigm to the Broadcast Congested Clique. We introduce an algorithm to compute spectral sparsifiers in a polylogarithmic number of rounds, which directly leads to an efficient Laplacian solver. Based on this primitive, we consider the linear program solver of Lee and Sidford [30].