  We observe returns of a simple random walk on a finite graph to a fixed node,
and would like to infer properties of the graph, in particular properties of
the spectrum of the transition matrix. This is not possible in general, but at
least the eigenvalues can be recovered under fairly general conditions, e.g.
when the graph has a node-transitive automorphism group. The main result is
that by observing polynomially many returns, it is possible to estimate the
spectral gap of such a graph up to a constant factor.
