TY - GEN

T1 - Guessing secrets efficiently via list decoding (extended abstract)

AU - Alon, Noga

AU - Guruswami, Venkatesan

AU - Kaufman, Tali

AU - Sudan, Madhu

PY - 2002

Y1 - 2002

N2 - We consider the guessing secrets problem defined by Chung, Graham, and Leighton [CGL01]. 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(logiV) questions together with an efficient (i.e., poly (log AT) time) algorithm to solve the guessing secrets problem for the case of 2 secrets. This answers the main algorithmic question left unanswered by [CGL01]. The main techniques we use are small e-biased spaces and the notion of list decoding. We also establish bounds on the number of questions needed to solve the A;-secrets game for k > 2, and discuss how list decoding can be used to get partial information about the secrets.

AB - We consider the guessing secrets problem defined by Chung, Graham, and Leighton [CGL01]. 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(logiV) questions together with an efficient (i.e., poly (log AT) time) algorithm to solve the guessing secrets problem for the case of 2 secrets. This answers the main algorithmic question left unanswered by [CGL01]. The main techniques we use are small e-biased spaces and the notion of list decoding. We also establish bounds on the number of questions needed to solve the A;-secrets game for k > 2, and discuss how list decoding can be used to get partial information about the secrets.

UR - http://www.scopus.com/inward/record.url?scp=24644438974&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=24644438974&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:24644438974

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 254

EP - 262

BT - Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002

PB - Association for Computing Machinery

T2 - 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002

Y2 - 6 January 2002 through 8 January 2002

ER -