  In this paper, we set forth a new algorithm for generating approximately
uniformly random spanning trees in undirected graphs. We show how to sample
from a distribution that is within a multiplicative $(1+\delta)$ of uniform in
expected time $\TO(m\sqrt{n}\log 1/\delta)$. This improves the sparse graph
case of the best previously known worst-case bound of $O(\min \{mn,
n^{2.376}\})$, which has stood for twenty years.
  To achieve this goal, we exploit the connection between random walks on
graphs and electrical networks, and we use this to introduce a new approach to
the problem that integrates discrete random walk-based techniques with
continuous linear algebraic methods. We believe that our use of electrical
networks and sparse linear system solvers in conjunction with random walks and
combinatorial partitioning techniques is a useful paradigm that will find
further applications in algorithmic graph theory.
