  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 (FOCS 2014). We show how to solve certain
linear programs up to additive error $\epsilon$ with $n$ constraints on an
$n$-vertex Broadcast Congested Clique network in $\tilde
O(\sqrt{n}\log(1/\epsilon))$ rounds. Using this, we show how to find an exact
solution to the minimum cost flow problem in $\tilde O(\sqrt{n})$ rounds.

Data Structures and Algorithms