Optimal Coin Flipping

Dexter Kozen ( Joseph Newton Pew, Jr. Professor in Engineering, Computer Science Department, Cornell University )

In this talk I will show how to simulate a coin of arbitrary real bias q with a coin of arbitrary real bias p with negligible loss of entropy.  I will derive an information-theoretic lower bound that is strictly larger than the Shannon entropy.  As a function of q, it is an everywhere discontinuous fractal.  There are efficient protocols that achieve the lower bound to within any desired accuracy, and achieve it exactly for p=1/2.  It is an open question whether there is a computable protocol that always achieves the lower bound for all rational p and q.