Guessing secrets efficiently via list decoding

We consider the guessing secrets problem defined by Chung et al. [2001]. This is a variant of the standard 20 questions game where the player has a set of k > 1 secrets from a universe of N possible secrets. The player is asked Boolean questions about the secret. For each question, the player picks one of the k secrets adversarially, and answers according to this secret. We present an explicit set of O (log N ) questions together with an efficient (i.e., poly(log N ) time) algorithm to solve the guessing secrets problem for the case of 2 secrets. This answers the main algorithmic question left unanswered by Chung et al. [2001]. The main techniques we use are small ϵ-biased spaces and the notion of list decoding . We also establish bounds on the number of questions needed to solve the k -secrets game for k > 2, and discuss how list decoding can be used to get partial information about the secrets, specifically to find a small core of secrets that must intersect the actual set of k secrets.