Sublinear-Time Sampling of Spanning Trees in the Congested Clique

We present the first sublinear-in-n round algorithm for sampling an approximately uniform spanning tree of an n-vertex graph in the CongestedClique model of distributed computing. In particular, our algorithm requires Õ (n0.657) rounds for sampling a spanning tree within total variation distance 1/nc, for arbitrary constant c > 0, from the uniform distribution. More precisely, our algorithm requires Õ (n1/2+α) rounds, where O (nα) is the running time of matrix multiplication in the CongestedClique model (currently α = 1-2/ω = 0.157, where ω is the sequential matrix multiplication time exponent). We can adapt our algorithm to give exact rather than approximate samples, but with a larger, though still o (n), runtime of Õ(n2/3+α) = O(n0.824).