Waiting for a bat to fly by (in polynomial time)

Itai Benjamini, Gady Kozma, Laszlo Lovasz +2

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 trans…