Event Detail

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

Speaker Info

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.