Tel Aviv University, Colloquium
Hello everyone,
The next colloquium talk will be held on:
Monday, 10/12/2012, 12:15, Schreiber 006, Tel Aviv University.
Speaker: Eyal Lubetzky (Microsoft Research and the University of Washington)
Title: Cutoff Phenomenon: Instant Randomness
The abstract is given below. Tea and coffee at 12:00, same room.
Hope to see you there. For information about future colloquia, see
Abstract: How many shuffles are needed to mix a deck of cards?
How long does it take a random walk on a transitive expander
to be suitably uniform? Is there a sharp threshold? For many
such questions the order of the mixing time is well understood,
and yet it is unknown whether mixing occurs gradually or abruptly.
The latter scenario, where the distance to equilibrium drops
from near 1 to near 0 over a negligible time period, corresponds
to the "cutoff phenomenon" discovered by Diaconis, Shahshahani
and Aldous in the early 80's. We will survey different aspects
of this topic, including recent results and some of the main
problems that remain open.