# Optimal Coin Flipping

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

- 16:30 30th September 2009 ( week -1, Michaelmas Term 2009 )Lecture Theater B (Joint with Departmental Seminar)

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.