Computer Science Department
McGregory Hall, 3rd Floor
13 Oak Drive
Hamilton, NY 13346
Charlotte Jablonski, Administrative Assistant
Start: Tuesday, November 27, 2012, 11:30 a.m.
End: Tuesday, November 27, 2012, noon
Location: CS department lounge
Title: Yao's Non-adaptive storage problem with 2 queries
Join us for a presentation and discussion by Prof. David Howard, Math department.
As usual, lunch will be available.
In this talk I will briefly describe a research problem I worked on that is located somewhere between mathematics and computer science. The problem involves a mathematical storage scheme.
At the Raider Inn there are n rooms and as this is a very special inn only m specific people in the whole world are allowed to spend the night in the inn. Furthermore as this inn is very popular every night it is completely filled with guests but only one person can stay per room. There are of course 13 managers in this hotel and they each know what the storage scheme for this hotel is (i.e. for any n set from the m people that stays in the hotel one night there is an exact predetermined assignment of rooms depending on the n set). Furthermore, for each member in the special m set of people there exist two special rooms (which are not necessarily uniquely assigned to the members of m) called their query rooms. These query rooms are special in the following way: Suppose a manager does not have the guest list for a particular night at the hotel; however, the manager wants to know if a particular person (call this person Jack) is in the hotel for the given evening. All this manager must do is find out who is staying in Jack's special query rooms and the manager can definitively answer whether Jack is staying in the hotel. (Note: the answer can be yes even if the manager did not see Jack in either query room.)
The question that arises given this set-up: How big can m be in relation to n?
I will briefly say what the going results are and, if time allows, future research directions for this topic.