Names in boxes

Description

The Names in boxes puzzle is presented by Peter Winkler (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; they may look into up to fifty 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 executed. There is a strategy that has a probability of success exceeding thirty percent - 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 compactly stored, so that EVERY data base query with a polynomial time algorithm can be answered by a sequential algorithm in time linear in the length of the query?