Title: Games, maps and randomness
Talk in the Logic Seminar
Abstract: Key problems in algorithmic information can be framed in terms
of maps on the reals as well as adversarial games on finite domains. In
the first part I will talk about the complexity of probabilistic
inversions of measure-preserving maps on the reals and report recent
progress on this topic. The second part will focus on reductions to
random reals and the associated open problems, which depend on solving
finite allocation games on the binary strings. My aim is to draw attention
to problems that originated in algorithmic information but can be stated,
motivated and studied (and perhaps solved) without specialized knowledge
or terminology.