Event Detail

Event Type: 
Department Colloquium
Tuesday, April 27, 2004 - 05:00

Speaker Info

University of California, Berkeley, visiting Microsoft Research

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.