{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T02:51:00Z","timestamp":1764557460202},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2019,2,11]],"date-time":"2019-02-11T00:00:00Z","timestamp":1549843200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2019,6]]},"DOI":"10.1007\/s00493-018-3803-4","type":"journal-article","created":{"date-parts":[[2019,2,11]],"date-time":"2019-02-11T02:46:25Z","timestamp":1549853185000},"page":"597-626","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Twenty (Short) Questions"],"prefix":"10.1007","volume":"39","author":[{"given":"Yuval","family":"Dagan","sequence":"first","affiliation":[]},{"given":"Yuval","family":"Filmus","sequence":"additional","affiliation":[]},{"given":"Ariel","family":"Gabizon","sequence":"additional","affiliation":[]},{"given":"Shay","family":"Moran","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,2,11]]},"reference":[{"key":"3803_CR1","volume-title":"Search problems","author":"R. Ahlswede","year":"1987","unstructured":"R. Ahlswede and I. Wegener: Search problems, John Wiley & Sons, Inc., New York, 1987."},{"key":"3803_CR2","doi-asserted-by":"publisher","first-page":"486","DOI":"10.1145\/103418.103469","volume-title":"Proceedings of the twenty-third annual ACM symposium on Theory of computing (STOC\u2019 91)","author":"J. A. Aslam","year":"1991","unstructured":"J. A. Aslam and A. Dhagat: Searching in the presence of linearly bounded errors, in: Proceedings of the twenty-third annual ACM symposium on Theory of computing (STOC\u2019 91), 486\u2013493, 1991."},{"key":"3803_CR3","volume-title":"Information Theory, Combinatorics, and Search Theory","year":"2013","unstructured":"H. Aydinian, F. Cicalese and C. Deppe, eds.: Information Theory, Combinatorics, and Search Theory, Springer-Verlag Berlin Heidelberg, 2013."},{"key":"3803_CR4","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1016\/0097-3165(75)90011-4","volume":"18","author":"D. W. Boyd","year":"1975","unstructured":"D. W. Boyd: The asymptotic number of solutions of a diophantine equation from coding theory, Journal of Combinatorial Theory, Ser. A\n                           18 (1975), 210\u2013215.","journal-title":"Journal of Combinatorial Theory, Ser. A"},{"key":"3803_CR5","first-page":"854","volume-title":"IEEE Transactions on Information Theory IT-32","author":"R. M. Capocelli","year":"1986","unstructured":"R. M. Capocelli, R. Giancarlo and I. J. Taneja: Bounds on the redundancy of Huffman codes, IEEE Transactions on Information Theory IT-32 (1986), 854\u2013857."},{"key":"3803_CR6","volume-title":"Elements of information theory","author":"T. M. Cover","year":"2006","unstructured":"T. M. Cover and J. A. Thomas: Elements of information theory (2. ed.), Wiley, 2006."},{"key":"3803_CR7","unstructured":"Y. Dagan, Y. Filmus and S. Moran: Comparison and equality queries achieve optimal redundancy, in preparation."},{"key":"3803_CR8","first-page":"16","volume-title":"Proceedings of 3rd Symposium on Discrete Algorithms (SODA\u201992)","author":"A. Dhagat","year":"1992","unstructured":"A. Dhagat, P. G\u00e1cs and P. Winkler: On playing \u201ctwenty questions\u201d with a liar, in: Proceedings of 3rd Symposium on Discrete Algorithms (SODA\u201992), 16\u201322, 1992."},{"key":"3803_CR9","doi-asserted-by":"publisher","first-page":"436","DOI":"10.1214\/aoms\/1177731363","volume":"14","author":"R. Dorfman","year":"1943","unstructured":"R. Dorfman: The detection of defective members of large populations, The Annals of Mathematical Statistics\n                           14 (1943), 436\u2013440.","journal-title":"The Annals of Mathematical Statistics"},{"key":"3803_CR10","doi-asserted-by":"publisher","DOI":"10.1142\/4252","volume-title":"Combinatorial Group Testing and Its Applications, volume 12 of Series on Applied Mathematics","author":"D.-Z. Du","year":"1999","unstructured":"D.-Z. Du and F. K. Hwang: Combinatorial Group Testing and Its Applications, volume 12 of Series on Applied Mathematics, World Scientific, 2nd edition, 1999."},{"key":"3803_CR11","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1016\/0304-3975(76)90078-5","volume":"1","author":"M. L. Fredman","year":"1976","unstructured":"M. L. Fredman: How good is the information theory bound in sorting? Theoretical Computer Science\n                           1 (1976), 355\u2013361.","journal-title":"Theoretical Computer Science"},{"key":"3803_CR12","first-page":"668","volume-title":"IEEE Transactions on Information Theory IT-24","author":"R. G. Gallager","year":"1987","unstructured":"R. G. Gallager: Variations on a theme by Huffman, IEEE Transactions on Information Theory IT-24 (1987), 668\u2013674."},{"key":"3803_CR13","doi-asserted-by":"publisher","first-page":"933","DOI":"10.1002\/j.1538-7305.1959.tb01583.x","volume":"38","author":"E. N. Gilbert","year":"1959","unstructured":"E. N. Gilbert and E. F. Moore: Variable-length binary encodings, Bell System Technical Journal\n                           38 (1959), 933\u2013967.","journal-title":"Bell System Technical Journal"},{"key":"3803_CR14","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1016\/S0019-9958(77)80011-9","volume":"34","author":"Y. Horibe","year":"1977","unstructured":"Y. Horibe: An improved bound for weight-balanced tree, Information and Control\n                           34 (1977), 148\u2013151.","journal-title":"Information and Control"},{"key":"3803_CR15","first-page":"1098","volume-title":"Proceedings of the I.R.E.","author":"D. A. Huffman","year":"1952","unstructured":"D. A. Huffman: A method for the construction of minimum-redundancy codes, in: Proceedings of the I.R.E., 1098\u20131103, 1952."},{"key":"3803_CR16","first-page":"220","volume-title":"IEEE Transactions on Information Theory IT-26","author":"O. Johnsen","year":"1980","unstructured":"O. Johnsen: On the redundancy of binary Huffman codes, IEEE Transactions on Information Theory IT-26 (1980), 220\u2013222."},{"key":"3803_CR17","volume-title":"A Survery of Combinatorial Theory","author":"Gy. O. H. Katona","year":"1973","unstructured":"Gy. O. H. Katona: Combinatorial search problems, in: J. N. Srivastava et al., editor, A Survery of Combinatorial Theory, North-Holland Publishing Company, 1973."},{"key":"3803_CR18","doi-asserted-by":"publisher","first-page":"1154","DOI":"10.1137\/12087222X","volume":"44","author":"P. Klein","year":"2015","unstructured":"P. Klein and N. E. Young: On the number of iterations for Dantzig-Wolfe optimization and packing-covering approximation algorithms, SIAM Journal on Computing\n                           44 (2015), 1154\u20131172.","journal-title":"SIAM Journal on Computing"},{"key":"3803_CR19","doi-asserted-by":"publisher","first-page":"606","DOI":"10.1007\/s00453-015-0061-3","volume":"75","author":"D. Krenn","year":"2016","unstructured":"D. Krenn and S. Wagner: Compositions into powers of b: asymptotic enumeration and parameters, Algorithmica\n                           75 (2016), 606\u2013631.","journal-title":"Algorithmica"},{"key":"3803_CR20","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/0097-3165(87)90029-X","volume":"44","author":"Z. Lonc","year":"1987","unstructured":"Z. Lonc and I. Rival: Chains, antichains, and fibres, Journal of Combinatorial Theory, Series A\n                           44 (1987), 207\u2013228.","journal-title":"Journal of Combinatorial Theory, Series A"},{"key":"3803_CR21","first-page":"144","volume-title":"IEEE Transactions on Information Theory IT-38","author":"D. Manstetten","year":"1992","unstructured":"D. Manstetten: Tight bounds on the redundancy of Huffman codes, IEEE Transactions on Information Theory IT-38 (1992), 144\u2013151."},{"key":"3803_CR22","first-page":"131","volume-title":"Information Theory Workshop (ITW\u2019 06)","author":"S. Mohajer","year":"2006","unstructured":"S. Mohajer, P. Pakzad and A. Kakhbod: Tight bounds on the redundancy of Huffman codes, in: Information Theory Workshop (ITW\u2019 06), 131\u2013135, 2006."},{"key":"3803_CR23","first-page":"156","volume-title":"IEEE Transactions on Information Theory IT-33","author":"B. L. Montgomery","year":"1987","unstructured":"B. L. Montgomery and J. Abrahams: On the redundancy of optimal binary prefix- condition codes for finite and infinite sources, IEEE Transactions on Information Theory IT-33 (1987), 156\u2013160."},{"key":"3803_CR24","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/s11083-015-9347-y","volume":"33","author":"S. Moran","year":"2016","unstructured":"S. Moran and A. Yehudayoff: A note on average-case sorting, Order\n                           33 (2016), 23\u201328.","journal-title":"Order"},{"key":"3803_CR25","first-page":"1225","volume-title":"IEEE Transactions on Information Theory IT-37","author":"N. Nakatsu","year":"1991","unstructured":"N. Nakatsu: Bounds on the redundancy of binary alphabetical codes, IEEE Transactions on Information Theory IT-37 (1991), 1225\u20131229."},{"key":"3803_CR26","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1147\/rd.172.0101","volume":"17","author":"J. Rissanen","year":"1973","unstructured":"J. Rissanen: Bounds for weight balanced trees, IBM Journal of Research and Development\n                           17 (1973), 101\u2013105.","journal-title":"IBM Journal of Research and Development"},{"key":"3803_CR27","doi-asserted-by":"publisher","first-page":"396","DOI":"10.1016\/0022-0000(80)90014-8","volume":"20","author":"R. L. Rivest","year":"1980","unstructured":"R. L. Rivest, A. R. Meyer, D. J. Kleitman, K. Winklmann and J. Spencer: Coping with errors in binary search procedures, Journal of Computer and System Sciences\n                           20 (1980), 396\u2013404.","journal-title":"Journal of Computer and System Sciences"},{"key":"3803_CR28","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1017\/S0963548300000080","volume":"1","author":"J. Spencer","year":"1992","unstructured":"J. Spencer and P. Winkler: Three thresholds for a liar, Combinatorics, Probability and Computing\n                           1 (1992), 81\u201393.","journal-title":"Combinatorics, Probability and Computing"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00493-018-3803-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-018-3803-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-018-3803-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,2,10]],"date-time":"2020-02-10T19:09:25Z","timestamp":1581361765000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00493-018-3803-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,2,11]]},"references-count":28,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,6]]}},"alternative-id":["3803"],"URL":"https:\/\/doi.org\/10.1007\/s00493-018-3803-4","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,2,11]]},"assertion":[{"value":"11 May 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 April 2018","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 February 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}