Monday, February 11, 2008
Humboldt-Universität zu Berlin
Institut für Informatik
Johann von Neumann-Haus
Rudower Chaussee 25
ATTENTION CHANGED: Haus I, 4. Etage, Raum 410.
Lecture - 14:15
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?