{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T06:04:17Z","timestamp":1775282657473,"version":"3.50.1"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2007,11,1]],"date-time":"2007-11-01T00:00:00Z","timestamp":1193875200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2007,11]]},"abstract":"<jats:p>\n            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\n            <jats:italic>k<\/jats:italic>\n            &gt; 1 secrets from a universe of\n            <jats:italic>N<\/jats:italic>\n            possible secrets. The player is asked Boolean questions about the secret. For each question, the player picks one of the\n            <jats:italic>k<\/jats:italic>\n            secrets adversarially, and answers according to this secret.\n          <\/jats:p>\n          <jats:p>\n            We present an explicit set of\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>N<\/jats:italic>\n            ) questions together with an efficient (i.e., poly(log\n            <jats:italic>N<\/jats:italic>\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\n            <jats:italic>\u03f5-biased spaces<\/jats:italic>\n            and the notion of\n            <jats:italic>list decoding<\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>\n            We also establish bounds on the number of questions needed to solve the\n            <jats:italic>k<\/jats:italic>\n            -secrets game for\n            <jats:italic>k<\/jats:italic>\n            &gt; 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\n            <jats:italic>k<\/jats:italic>\n            secrets.\n          <\/jats:p>","DOI":"10.1145\/1290672.1290679","type":"journal-article","created":{"date-parts":[[2007,11,30]],"date-time":"2007-11-30T14:24:58Z","timestamp":1196432698000},"page":"42","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Guessing secrets efficiently via list decoding"],"prefix":"10.1145","volume":"3","author":[{"given":"Noga","family":"Alon","sequence":"first","affiliation":[{"name":"Tel Aviv University, Tel Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Venkatesan","family":"Guruswami","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, WA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tali","family":"Kaufman","sequence":"additional","affiliation":[{"name":"Institute for Advanced Study, Princeton, NJ"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Madhu","family":"Sudan","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, MA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2007,11]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.119713"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcta.2001.3177"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240030308"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms (SODA), 254-- 262","author":"Alon N.","unstructured":"Alon , N. , Guruswami , V. , Kaufman , T. , and Sudan , M . 2002. Guessing secrets efficiently via list decoding . In Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms (SODA), 254-- 262 . Alon, N., Guruswami, V., Kaufman, T., and Sudan, M. 2002. Guessing secrets efficiently via list decoding. In Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms (SODA), 254-- 262."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480100376848"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the Conference of Advances in Cryptology (CRYPTO), Y. Desmedt, ed. Lecture Notes in Computer Science","volume":"839","author":"Chor B.","unstructured":"Chor , B. , Fiat , A. , and Naor , M . 1994. Tracing traitors . In Proceedings of the Conference of Advances in Cryptology (CRYPTO), Y. Desmedt, ed. Lecture Notes in Computer Science , vol. 839 . Springer, Berlin, 257--270. Chor, B., Fiat, A., and Naor, M. 1994. Tracing traitors. In Proceedings of the Conference of Advances in Cryptology (CRYPTO), Y. Desmedt, ed. Lecture Notes in Computer Science, vol. 839. Springer, Berlin, 257--270."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.37236\/1557"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms (SODA), 247--253","author":"Chung F.","unstructured":"Chung , F. , Graham , R. , and Lu , L . 2002. Guessing secrets with inner product questions . In Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms (SODA), 247--253 . Chung, F., Graham, R., and Lu, L. 2002. Guessing secrets with inner product questions. In Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms (SODA), 247--253."},{"key":"e_1_2_1_9_1","unstructured":"Cohen G. D. Encheva S. B. and Schaathun H. G. 2001. On separating codes. Tech. Rep. Ecole Nationale Sup\u00e9rieure des T \u00e9l\u00e9communications Paris.  Cohen G. D. Encheva S. B. and Schaathun H. G. 2001. On separating codes. Tech. Rep. Ecole Nationale Sup\u00e9rieure des T \u00e9l\u00e9communications Paris."},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the Colloqmium of the Math Society Janos Bolyai, 10","author":"Erd\u0151s P.","unstructured":"Erd\u0151s , P. and Lov\u00e1sz , L . 1975. In Infinite and Finite Sets , Proceedings of the Colloqmium of the Math Society Janos Bolyai, 10 , Problems and results on 3-chromatic hypergraphs and some related questions. North-Holland, Amsterdam, 609--627. Erd\u0151s, P. and Lov\u00e1sz, L. 1975. In Infinite and Finite Sets, Proceedings of the Colloqmium of the Math Society Janos Bolyai, 10, Problems and results on 3-chromatic hypergraphs and some related questions. North-Holland, Amsterdam, 609--627."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276855"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.782097"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335327"},{"key":"e_1_2_1_14_1","unstructured":"Guruswami V. and Sudan M. 2001. Extensions to the Johnson bound. manuscript. http:\/\/people.csail.mit.edu\/madhu\/papers\/johnson.ps.  Guruswami V. and Sudan M. 2001. Extensions to the Johnson bound. manuscript. http:\/\/people.csail.mit.edu\/madhu\/papers\/johnson.ps."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcta.1997.2851"},{"key":"e_1_2_1_16_1","unstructured":"I've Got a Secret. 1952. I've got a secret. http:\/\/www.timvp.com\/ivegotse.html.  I've Got a Secret. 1952. I've got a secret. http:\/\/www.timvp.com\/ivegotse.html."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(73)90098-8"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/0401035"},{"key":"e_1_2_1_19_1","volume-title":"Tech. Rep. CS2001-0687","author":"Micciancio D.","unstructured":"Micciancio , D. and Segerlind , N . 2001. Guessing two secrets with small queries . Tech. Rep. CS2001-0687 , Computer Science and Engineering Department, University of California at San Diego. November. Micciancio, D. and Segerlind, N. 2001. Guessing two secrets with small queries. Tech. Rep. CS2001-0687, Computer Science and Engineering Department, University of California at San Diego. November."},{"key":"e_1_2_1_20_1","unstructured":"Micciancio D. and Segerlind N. 2004. Using hypergraph homomorphisms to guess three secrets. manuscript.  Micciancio D. and Segerlind N. 2004. Using hypergraph homomorphisms to guess three secrets. manuscript."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222053"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society","author":"Naor M.","unstructured":"Naor , M. , Schulman , L. J. , and Srinivasan , A . 1995. Splitters and near-optimal derandomization . In Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society , Washington, DC, 182. Naor, M., Schulman, L. J., and Srinivasan, A. 1995. Splitters and near-optimal derandomization. In Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society, Washington, DC, 182."},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Nielsen R. R. and H\u00f8holdt T. 2000. Decoding Reed-Solomon codes beyond half the minimum distance. In Coding Theory Cryptography and Related Areas Buchmann et al. eds. Springer Berlin 221--236.  Nielsen R. R. and H\u00f8holdt T. 2000. Decoding Reed-Solomon codes beyond half the minimum distance. In Coding Theory Cryptography and Related Areas Buchmann et al. eds. Springer Berlin 221--236.","DOI":"10.1007\/978-3-642-57189-3_20"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2005.10129099"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.817522"},{"key":"e_1_2_1_26_1","first-page":"105","article-title":"Separating systems","volume":"30","author":"Segalovich Y. L.","year":"1994","unstructured":"Segalovich , Y. L. 1994 . Separating systems . Problems Inf. Transm. 30 , 2, 105 -- 123 . Segalovich, Y. L. 1994. Separating systems. Problems Inf. Transm. 30, 2, 105--123.","journal-title":"Problems Inf. Transm."},{"key":"e_1_2_1_27_1","volume-title":"Introduction to Coding Theory","author":"van Lint J. H.","unstructured":"van Lint , J. H. 1999. Introduction to Coding Theory , 3 rd ed. Graduate Texts in Mathematics, vol. 86 . Springer , Berlin. van Lint, J. H. 1999. Introduction to Coding Theory, 3rd ed. Graduate Texts in Mathematics, vol. 86. Springer, Berlin.","edition":"3"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1290672.1290679","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1290672.1290679","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T14:52:24Z","timestamp":1750258344000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1290672.1290679"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,11]]},"references-count":27,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2007,11]]}},"alternative-id":["10.1145\/1290672.1290679"],"URL":"https:\/\/doi.org\/10.1145\/1290672.1290679","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,11]]},"assertion":[{"value":"2007-11-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}