Monday, February 11, 2008
Humboldt-Universität zu Berlin
Institut für Informatik
Johann von Neumann-Haus
Rudower Chaussee 25
12489 Berlin
ATTENTION CHANGED: Haus I, 4. Etage, Raum 410.
Lecture - 14:15
Abstract:
The "Names in boxes" puzzle is presented by
Peter Wrinkler (College Math. J, vol 37:4, page 260)
as follows:
"The names of one hundred prisoners are placed
in one hundred wooden boxes, one name to each
box, and the boxes are lined up on a table in a
room. One by one, the prisoners are led into the
room; thy may look into up to fiffy of the boxes to try
to find their own name but must leave the room exactly
as it was. They are permitted no further communication
after leaving the room. The prisoners have a chance to
plot a strategy in advance and they are going to need
it, because unless they all find their own names they
will all be exectued. There is a strategy that has a
probability of success exceeding thirty procent - find
it"
The puzzle first appeared (in a somewhat less elegant
version) in Anna Gal and Peter Bro Miltersen, "The cell
probe complexity of succinct data structures", at ICALP 2003.
In this talk we present the history of the puzzle
and explain its original motivation from the study
of cell probe complexity, a combinatorial theory of
compact representation and retrieval of data.
In particular, we explain how the "Names in boxes" puzzle
relates to the following fundamental question of data
retrieval: Can data be stored, so that EVERY data
base query with a polynomial time algorithm can be answered
in logarithmic time by a sequential algorithm?