Guessing secrets efficiently via list decoding
Guessing secrets efficiently via list decoding
复制标题
通过列表解码有效猜测秘密
DOI：
--
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
M. Sudan
中科院分区：
文献类型：
--
作者：
N. Alon;V. Guruswami;T. Kaufman;M. Sudan
我们考虑Chung，Graham和Leighton [CGL 01]定义的猜测秘密问题。这是一个标准的20个问题的游戏，其中玩家有一组k > 1的秘密从一个宇宙的N个可能的秘密。玩家被问到关于每个问题的秘密的布尔问题，玩家从k个秘密中选择一个，并根据这个秘密回答。我们提出了一个显式的O（log N）问题集以及一个有效的（即，Poly（log N）time）算法来解决2个秘密的情况下的猜测秘密问题。这回答了[CGL 01]未回答的主要算法问题。我们使用的主要技术是小ε-有偏空间和列表解码的概念，我们还建立了解决k-秘密博弈（k > 2）所需问题的数量的界，并讨论了如何使用列表解码来获得关于秘密的部分信息。
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(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 [CGL01]. 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.