Guessing secrets efficiently via list decoding

Noga Alon, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan

Research output: Contribution to journalArticle

5 Scopus citations

Abstract

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.

Original languageEnglish (US)
Article number1290679
JournalACM Transactions on Algorithms
Volume3
Issue number4
DOIs
StatePublished - Nov 1 2007
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Mathematics (miscellaneous)

Keywords

  • 20 questions
  • Biased spaces
  • Decoding algorithms
  • Error-correcting codes
  • K-universal sets

Fingerprint Dive into the research topics of 'Guessing secrets efficiently via list decoding'. Together they form a unique fingerprint.

  • Cite this