The seminar covers a wide range of topics in pure and applied probability and in mathematical physics. Unless otherwise noted, the talks take place on Fridays, 11am-12noon, in room WWH 512. See directions to the Courant Institute.
What can one say about a graph from multiple (short) random walk trajectories on it? In this talk we consider algorithms that only "see" walk trajectories and the degrees along the way.
We will show that the number of vertices, edges and mixing time can be all estimated with a number of RW steps that is sublinear in the size of the graph and in its mixing or relaxation time. Our bounds on the number of RW steps are optimal up to constant or polylog factors. We also argue that such algorithms cannot "know when to stop", and discuss additional conditions that circumvent this limitation. To prove our results, we rely on bounds for random walk intersections by Peres, Sauerwald, Sousi and Stauffer.
Joint with Anna Ben-Hamou (Sorbonne) and Yuval Peres (MSR).