Unbiased Coin Tossing With a Biased Coin

by Mr Santanu Dey (School of Technology and Computer Science)

Friday 4 May 2012, 15:00 → 16:30 Asia/Kolkata

A-212 (STCS Seminar Room) (Colaba Campus)

I will discuss some algorithms for simulating a flip of an unbiased coin by flipping a coin of unknown bias. We will discuss efficiency of several algorithms, where the expected number of flips is our measure of efficiency. We will also outline the proof of a conjecture by Hoeffding and Simons that there is no optimal algorithm.