Department of Mathematics
Title : Problems for the clairvoyant demon
| Speaker: Professor Geoffrey Grimmett Affiliation: University of Cambridge Time: 2:00 pm Thursday, 3 May, 2012 Location: Building 423 Room 342, 22 Symonds street |
Abstract
| The clairvoyant demon can see into the future. But how does this help “it” to do its work? The first demon problem originated in theoretical computer science. It stimulated an interest in such questions, and has provoked two further `easy-to-state but hard-tosolve’ problems. I will describe three apparently simple problems for the demon involving infinite sequences of coin tosses. Two of these problems were formulated by Peter Winkler. The third problem is provocative and unsolved. It asks whether one random sequence may be embedded within another. There are connections to earlier work by others on biLipschitz embeddings and quasiisometries, and even to the Borsuk-Ulam theorem of topological combinatorics. |
-
Programmes and Centres
- New Zealand Institute of Mathematics and its Applications (NZIMA)
- Community for Understanding and Learning in the Mathematical Sciences (CULMS)
- Centre for Mathematical Social Science (CMSS)
- Department of Computer Science
- Department of Engineering Science
- Department of Physics
- Department of Statistics
- Auckland Bioengineering Institute
