Event Type:

Department Colloquium

Date/Time:

Tuesday, April 27, 2004 - 05:00

Guest Speaker:

Yuval Peres

Institution:

University of California, Berkeley, visiting Microsoft Research

Abstract:

Randomized algorithms are crucial in modern computer science. In this talk we describe two examples of influence going the other way. 1. Unbiasing and simulation given a coin with unknown bias: Suppose that we are given a coin with an unknown probability p of heads. By tossing this coin repeatedly, can we simulate an unbiased coin? how about a coin with probability 2p of heads (when phttp://www.math.ubc.ca/~holroyd/stable.html .There is a unique "fair" allocation that is "stable" in the sense of the Gale-Shapley stable marriage problem. Every point of M is assigned a bounded region with finitely many components, but obtaining any(!) tail estimate for the diameter of these regions is open.