Georgia Institute of Technology College of Sciences

We present an algorithm that, with high probability, generates a random spanning treefrom an edge-weighted undirected graph in O (n^{5/3}m^{1/3}) time. The tree is sampled from adistribution where the probability of each tree is proportional to the product of its edge weights.This improves upon the previous best algorithm due to Colbourn et al. that runs in matrix multiplication time, O(n^\omega). For the special case of unweighted graphs, this improves upon thebest previously known running time of ˜O(min{n^\omega, mn^{1/2}, m^{4/3}}) for m >> n^{7/4} (Colbourn et al. ’96, Kelner-Madry ’09, Madry et al. ’15).The effective resistance metric is essential to our algorithm, as in the work of Madry et al., butwe eschew determinant-based and random walk-based techniques used by previous algorithms.Instead, our algorithm is based on Gaussian elimination, and the fact that effective resistance ispreserved in the graph resulting from eliminating a subset of vertices (called a Schur complement).As part of our algorithm, we show how to compute -approximate effective resistances for a set Sof vertex pairs via approximate Schur complements in O (m + (n + |S|)/\eps^{ −2}) time, without usingthe Johnson-Lindenstrauss lemma which requires eO(min{(m+|S|) \eps{−2},m+n /eps^{−4} +|S|/eps^{ −2}}) time. We combine this approximation procedure with an error correction procedure for handing edges where our estimate isn’t sufficiently accurate.Joint work with Rasmus Kyng, John Peebles, Anup Rao, and Sushant Sachdeva