# Guessing Secrets

### 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.