CAGT Seminar: Peter Bro Miltersen: The "Names in boxes" game
2007.11.07 |
| Date | Tue Nov 27 |
| Time | 14:15 — 15:15 |
| Location | DI-Turing-014 |
Title: The "Names in boxes" game and the problem of efficiently answering EVERY database query
Speaker: Peter Bro Miltersen
Time: Tue Nov 27th 2007 14:15-15:15
Location: Turing-014
Abstract:
The "Names in boxes" game 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. Theprisoners 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 game first appeared (in a somewhat lesselegant 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 game 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" game 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?