Courant Institute Probability and Mathematical Physics seminar


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.

Lisa Hartung and Thomas Leblé help organizing, in behalf of the Probability/Mathematical physics group. To be kept informed, you can subscribe to the Probability Seminar Mailing list.
Old webpage.

Fall 2018

September 7th, 2018
(): .

September 14th, 2018
(): .

September 21th, 2018
(): .

September 28th, 2018
(): .

October 5th, 2018
(): .

October 12th, 2018
Anirban Basak (Weizmann Institute): .

October 19th, 2018
Roberto 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 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).

October 26th, 2018
Elliot Paquette (Ohio State): .

November 2nd, 2018
(): .

November 9th, 2018
Duncan Dauvergne (U. Toronto): .

November 16th, 2018
(): .

November 23th, 2018
November 30th, 2018
(): .

December 7th, 2018
(): .

December 14th, 2018
(): .