Sampling random spanning trees faster than matrix multiplication.

David Durfee Rasmus Kyng John Peebles Anup B. Rao Sushant Sachdeva

Published in: STOC (2017)

Keyphrases

spanning tree
matrix multiplication
edge disjoint
message passing
minimum cost
minimum spanning tree
sampled data
minimum spanning trees
matrix factorization
distributed memory
random sampling
three dimensional
multistage
highly efficient
parallel implementation