Probability and Mathematical Physics Seminar

Estimating graph parameters via multiple random walks

Location: Warren Weaver Hall 512

Date: Friday, October 12, 2018, 10:15 a.m.

Synopsis:

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).