Eastern Great Lakes Theory Workshop Talk

Optimal Coin Flipping

Dexter Kozen, Cornell University

Sunday, October 4, 9:00-10:00am

ABSTRACT

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.

Speaker Bio

Dexter Kozen is the Joseph Newton Pew, Jr. Professor in Engineering at Cornell University. He received his undergraduate degree from Dartmouth College in mathematics in 1974 and his PhD from Cornell in computer science in 1977. After working as a member of the research staff at the IBM Thomas J. Watson Research Center for several years, he returned to Ithaca to join the Cornell faculty in computer science in 1985. He is a recipient of the John G. Kemeny Prize in Computing and an IBM Outstanding Innovation Award, and is a former John Simon Guggenheim fellow and a fellow of the Association of Computing Machinery and American Association for the Advancement of Science.

Kozen's research interests span a variety of topics on the boundary of computer science and mathematics: design and analysis of algorithms, computation complexity theory, complexity of decision problems in logic and algebra, and logics and semantics of programming languages. He is the author of four books and over 150 research articles.

Kozen lives with his wife Frances, an extension associate in the College of Human Ecology at Cornell. They have three sons, Alex 25, a PhD student at the University of Maryland, Geoff 23, a legal aid assistant in Ithaca, and Tim 20, a junior at Cornell. For leisure activities, he enjoys music of all types, but especially modern rock. He can be seen occasionally playing guitar with a local Ithaca rock band. He also enjoys sports, especially rugby, ice hockey, and skiing.

< Schedule < EaGL-II homepage