Talk 10590 data/Fall

Probability Seminar
Tuesday, December 4, 2018, 3:15pm, 119 Physics
Roberto I. Oliveira (IMPA)
Estimating graph parameters via multiple random walks

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 analyse our results, we rely on novel bounds for random walk intersections. The lower bounds come from a family of explicit constructions. [video]

Generated at 8:56am Thursday, April 25, 2024 by Mcal. Top * Reload * Login