Abstract
We will see that the cover time of a graph (i.e., any finite state reversible Markov chain) can be computed in near-linear time using Laplacian solvers. In fact, the algorithm is simple enough to be contained in this abstract: Calculate |E|*max(sqrt{L+} (g_1, ..., g_n))^2 where L+ is the pseudo-inverse of the combinatorial Laplacian, {g_i} are i.i.d. N(0,1) random variables, and |E| is the number of edges.
In joint work with Jian Ding and Yuval Peres, we discovered this connection and proved that the estimate is accurate up to an O(1) factor. Recent work of Alex Zhai (a graduate student at Stanford) shows that the approximation is accurate up to a 1+o(1) factor and completes a beautiful picture relating the set of uncovered vertices to the extrema of the underlying Gaussian free field.