Fast Spanning Tree Sampling in Broadcast Congested Clique
This solves a fundamental graph problem in distributed computing for researchers and practitioners, with incremental improvements in efficiency.
The paper tackles the problem of sampling a random spanning tree in the Broadcast Congested Clique model, achieving the first polylogarithmic-round algorithm that outputs a sample with total variation distance at most O(n^{-c}) from uniform in c * log^{O(1)}(n) rounds, which is an exponential improvement over prior work.
We present the first polylogarithmic-round algorithm for sampling a random spanning tree in the (Broadcast) Congested Clique model. For any constant $c > 0$, our algorithm outputs a sample from a distribution whose total variation distance from the uniform spanning tree distribution is at most $O(n^{-c})$ in at most $c \cdot \log^{O(1)}(n)$ rounds. The exponent hidden in $\log^{O(1)}(n)$ is an absolute constant independent of $c$ and $n$. This is an exponential improvement over the previous best algorithm of Pemmaraju, Roy, and Sobel (PODC 2025) for the Congested Clique model.