{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:52:22Z","timestamp":1787320342994,"version":"build-2736575974"},"reference-count":16,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1337\/16"],"award-info":[{"award-number":["1337\/16"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2024,3,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>In the distributional Twenty Questions game, Bob chooses a number [Formula: see text] from 1 to [Formula: see text] according to a distribution [Formula: see text], and Alice (who knows [Formula: see text]) attempts to identify [Formula: see text] using yes\/no questions, which Bob answers truthfully. Her goal is to minimize the expected number of questions. The optimal strategy for the Twenty Questions game corresponds to a Huffman code for [Formula: see text], yet this strategy could potentially uses all [Formula: see text] possible questions. Dagan et\u00a0al. constructed a set of [Formula: see text] questions which suffice to construct an optimal strategy for all [Formula: see text], and showed that this number is optimal (up to subexponential factors) for infinitely many [Formula: see text]. We determine the optimal size of such a set of questions for all [Formula: see text] (up to subexponential factors), answering an open question of Dagan et\u00a0al. In addition, we generalize the results of Dagan et\u00a0al. to the [Formula: see text]-ary setting, obtaining similar results with 1.25 replaced by [Formula: see text].<\/jats:p>","DOI":"10.1137\/21m1424494","type":"journal-article","created":{"date-parts":[[2024,1,19]],"date-time":"2024-01-19T04:51:59Z","timestamp":1705639919000},"page":"412-452","source":"Crossref","is-referenced-by-count":0,"title":["Optimal Sets of Questions for Twenty Questions"],"prefix":"10.1137","volume":"38","author":[{"given":"Yuval","family":"Filmus","sequence":"first","affiliation":[{"name":"The Henry and Marilyn Taub Faculty of Computer Science, Technion, Haifa, 3200003, Israel."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Idan","family":"Mehalel","sequence":"additional","affiliation":[{"name":"The Henry and Marilyn Taub Faculty of Computer Science, Technion, Haifa, 3200003, Israel."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2024,1,19]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36899-8"},{"key":"ref2","volume-title":"Search Problems","author":"Ahlswede R.","year":"1987"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1007\/BF00993277"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1561\/9781933019543"},{"key":"ref5","unstructured":"T. M. Cover and J. A. Thomas, Elements of Information Theory, Wiley-Interscience, Hoboken, NJ, 2006."},{"key":"ref6","doi-asserted-by":"crossref","unstructured":"Y. Dagan, Y. Filmus, A. Gabizon, and S. Moran, Twenty (simple) questions, in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, 2017, pp. 9\u201321.","DOI":"10.1145\/3055399.3055422"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-018-3803-4"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177731363"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1017\/S144678870000238X"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1137\/0403017"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1109\/JRPROC.1952.273898"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-7204-2262-7.50028-4"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(87)90029-X"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1948.tb01338.x"},{"key":"ref15","author":"Young N.","year":"2012","journal-title":"Theoretical Computer Science Stack Exchange"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1959.11989389"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/21M1424494","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T12:56:56Z","timestamp":1787317016000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/21M1424494"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,19]]},"references-count":16,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3,31]]}},"alternative-id":["10.1137\/21M1424494"],"URL":"https:\/\/doi.org\/10.1137\/21m1424494","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,1,19]]}}}