A technical device used by the paper (and many of its predecessors) to find "good" cycles to sample is a new concept to me: that of "low-stretch" spanning trees. From the MIT news article:
This animation shows two different "spanning trees" for a simple graph, a grid like those used in much scientific computing. The speedups promised by a new MIT algorithm require "low-stretch" spanning trees (green), in which the paths between neighboring nodes don't become excessively long (red).
Given any spanning tree, you get a basis of the vector space of linear combinations of oriented edges of the graph (called the "cycle space" of the graph) by considering the edges not in the spanning tree: each such edge (a,b) gives you a cycle in combination with the unique path P from a to b in the spanning tree. In a low-stretch spanning tree, special thing is that these cycles aren't very big very often. It's not just a basis of the cycle space, it's somehow a nice, small basis.
Anyway lots of other ideas in this paper, still haven't finished reading it, but it's really neat.
