Guessing Secrets

Fan Chung, Ronald Graham, Tom Leighton

Abstract


Suppose we are given some fixed (but unknown) subset $X$ of a set $\Omega$, and our object is to learn as much as possible about the elements of $X$ by asking binary questions. Specifically, each question is just a function $F: \Omega \rightarrow \{0,1\}$, and the answer to $F$ is just the value $F(X_i)$ for some $X_i \in X$, (determined, for example, by a potentially malevolent but truthful, adversary). In this paper, we describe various algorithms for solving this problem, and establish upper and lower bounds on the efficiency of such algorithms.


Full Text: PDF