### DIMACS Theoretical Computer Science Seminar

Title: The Hat Problem and Autoreductions of Random Sequences

Speaker: **Wolfgang Merkle**, University of Heidelberg

Date: Wednesday, September 26, 2007 11:00-12:00pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

The hat problem asks for a strategy for the following game. Each of n
Players is assigned a blue or red hat according to independent tosses of a
fair coin. Each player knows the colors of all other hats but not of his own
hat. The player collaborate as a team, the team wins if at least one player
guesses his or her own color correctly and no player guesses incorrectly,
while any player may abstain from guessing. The players can agree on an
arbitrarily complex strategy before the game starts but cannot communicate during
the game.

The talk will discuss an optimal strategy for the hat problem where the probability
of success goes to 1 when the number of players increases. The strategy will then
be applied to autoreductions of infinite random sequences, which are considered
in the field of algorithmic randomness. The main result is that for appropriate
types of random sequences and models of autoreductions, the bits of a random
sequence depend on each other in such a way that infinitely many bits may be computed
from the remaining bits, while it is not possible to compute this way a constant
nonzero fraction of all bits.