Determining membership with 2 simultaneous queries
Alice and Bob are playing a cooperative game in which Alice must devise a scheme to store n elements in an array from a universe U of size m . Her goal is to store in such a way that for every x?U x ? U Bob can observe the values of two positions (dependent on x) in the array and determine whether x is in the array or not. Alice may share her storage scheme with Bob and they win if such an arrangement is made. The question is how large can the universe U be in terms of n so that Alice and Bob can win? In this paper we give upper and lower bounds on this question for general n  and the special case when n=3 n = 3 . We also pose conjectures and further questions for research.
membership searching sorting information retrieval cell-probe