{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T14:38:00Z","timestamp":1787495880519,"version":"build-2736575974"},"publisher-location":"New York, NY, USA","reference-count":121,"publisher":"ACM","license":[{"start":{"date-parts":[[2017,6,19]],"date-time":"2017-06-19T00:00:00Z","timestamp":1497830400000},"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":[],"published-print":{"date-parts":[[2017,6,19]]},"DOI":"10.1145\/3055399.3055422","type":"proceedings-article","created":{"date-parts":[[2017,6,15]],"date-time":"2017-06-15T16:27:45Z","timestamp":1497544065000},"page":"9-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Twenty (simple) questions"],"prefix":"10.1145","author":[{"given":"Yuval","family":"Dagan","sequence":"first","affiliation":[{"name":"Technion, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yuval","family":"Filmus","sequence":"additional","affiliation":[{"name":"Technion, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ariel","family":"Gabizon","sequence":"additional","affiliation":[{"name":"Zerocoin Electronic Coin, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shay","family":"Moran","sequence":"additional","affiliation":[{"name":"University of California at San Diego, USA \/ Simons Institute for the Theory of Computing Berkeley, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2017,6,19]]},"reference":[{"key":"e_1_3_2_2_1_1","unstructured":"Julia Abrahams. 1997.  Julia Abrahams. 1997."},{"key":"e_1_3_2_2_2_1","unstructured":"Code and parse trees for lossless source encoding. In Compression and Complexity of Sequences. 145\u2013171.  Code and parse trees for lossless source encoding. In Compression and Complexity of Sequences. 145\u2013171."},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1779"},{"key":"e_1_3_2_2_4_1","unstructured":"Rudolf Ahlswede and Ingo Wegener. 1987.  Rudolf Ahlswede and Ingo Wegener. 1987."},{"key":"e_1_3_2_2_5_1","unstructured":"Search problems. John Wiley & Sons Inc. New York.  Search problems. John Wiley & Sons Inc. New York."},{"key":"e_1_3_2_2_6_1","unstructured":"Nir Ailon and Bernard Chazelle. 2005.  Nir Ailon and Bernard Chazelle. 2005."},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1059513.1059515"},{"key":"e_1_3_2_2_8_1","unstructured":"Richard Anderson Sampath Kannan Howard Karloff and Richard E. Ladner. 2002.  Richard Anderson Sampath Kannan Howard Karloff and Richard E. Ladner. 2002."},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(02)00203-1"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103469"},{"key":"e_1_3_2_2_11_1","unstructured":"Harout Aydinian Ferdinando Cicalese and Christian Deppe (Eds.). 2013.  Harout Aydinian Ferdinando Cicalese and Christian Deppe (Eds.). 2013."},{"key":"e_1_3_2_2_12_1","unstructured":"Information Theory Combinatorics and Search Theory. Springer-Verlag Berlin Heidelberg.  Information Theory Combinatorics and Search Theory. Springer-Verlag Berlin Heidelberg."},{"key":"e_1_3_2_2_13_1","volume-title":"IEEE International Symposium on Information Theory (ISIT","author":"Baer Michael B.","year":"2007"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979731858X"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808735"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03367-4_21"},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1986.1057239"},{"key":"e_1_3_2_2_18_1","first-page":"1","article-title":"Solving k-SUM using few linear queries. In 24th Annual European Symposium on Algorithms (ESA 2016)","volume":"25","author":"Cardinal Jean","year":"2016","journal-title":"LIPIcs"},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"crossref","unstructured":"Marek Chrobak Mordecai Golin J. Ian Munro and Neal E. Young. 2015. Optimal Search Trees with 2-Way Comparisons. In Algorithms and Computation (ISAAC 2015). 71\u201382.  Marek Chrobak Mordecai Golin J. Ian Munro and Neal E. Young. 2015. Optimal Search Trees with 2-Way Comparisons. In Algorithms and Computation (ISAAC 2015). 71\u201382.","DOI":"10.1007\/978-3-662-48971-0_7"},{"key":"e_1_3_2_2_20_1","unstructured":"David Cohn Les Atlas and Richard Ladner. 1994.  David Cohn Les Atlas and Richard Ladner. 1994."},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022673506211"},{"key":"e_1_3_2_2_22_1","volume-title":"Surveys in Combinatorics","volume":"187","author":"Colbourn C. J.","year":"1993"},{"key":"e_1_3_2_2_23_1","unstructured":"Thomas M. Cover and Joy A. Thomas. 2006.  Thomas M. Cover and Joy A. Thomas. 2006."},{"key":"e_1_3_2_2_24_1","unstructured":"Elements of information theory (2. ed.). Wiley.  Elements of information theory (2. ed.). Wiley."},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90212-R"},{"key":"e_1_3_2_2_26_1","volume-title":"Liar. In Proceedings of 3rd Symposium on Discrete Algorithms (SODA\u201992)","author":"Dhagat Aditi","year":"1992"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177731363"},{"key":"e_1_3_2_2_28_1","unstructured":"Ding-Zhu Du and Frank K. Hwang. 1999.  Ding-Zhu Du and Frank K. Hwang. 1999."},{"key":"e_1_3_2_2_29_1","volume-title":"Combinatorial Group Testing and Its Applications","edition":"2"},{"key":"e_1_3_2_2_30_1","unstructured":"Dwight Duffus Bill Sands and Peter Winkler. 1990.  Dwight Duffus Bill Sands and Peter Winkler. 1990."},{"key":"e_1_3_2_2_31_1","volume-title":"Twenty (Simple) Questions STOC\u201917","author":"Maximal","year":"2017"},{"key":"e_1_3_2_2_32_1","unstructured":"Jeff Erickson. 1999.  Jeff Erickson. 1999."},{"key":"e_1_3_2_2_33_1","unstructured":"Lower bounds for linear satisfiability problems. Chicago Journal of Theoretical Computer Science 8 (1999).  Lower bounds for linear satisfiability problems. Chicago Journal of Theoretical Computer Science 8 (1999)."},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(03)00094-4"},{"key":"e_1_3_2_2_35_1","unstructured":"Ester Ezra and Micha Sharir. 2016. The Decision Tree Complexity for k-SUM is at most Nearly Quadratic. Manuscript. (2016).  Ester Ezra and Micha Sharir. 2016. The Decision Tree Complexity for k-SUM is at most Nearly Quadratic. Manuscript. (2016)."},{"key":"e_1_3_2_2_36_1","volume-title":"Record of the 7th Asilomar Conference on Circuits, Systems, and Computers. 593\u2013597","author":"Faller Newton","year":"1973"},{"key":"e_1_3_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90078-5"},{"key":"e_1_3_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-015-0079-6"},{"key":"e_1_3_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1978.1055959"},{"key":"e_1_3_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/0203008"},{"key":"e_1_3_2_2_41_1","unstructured":"Michael R. Garey and Ronald L. Graham. 1974.  Michael R. Garey and Ronald L. Graham. 1974."},{"key":"e_1_3_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00263588"},{"key":"e_1_3_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/0206045"},{"key":"e_1_3_2_2_44_1","unstructured":"Edgar N. Gilbert. 1971.  Edgar N. Gilbert. 1971."},{"key":"e_1_3_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1971.1054638"},{"key":"e_1_3_2_2_46_1","unstructured":"E. N. Gilbert and E. F. Moore. 1959.  E. N. Gilbert and E. F. Moore. 1959."},{"key":"e_1_3_2_2_47_1","doi-asserted-by":"crossref","unstructured":"Variable-Length Binary Encodings. Bell System Technical Journal 38 (1959) 933\u2013967.  Variable-Length Binary Encodings. Bell System Technical Journal 38 (1959) 933\u2013967.","DOI":"10.1002\/j.1538-7305.1959.tb01583.x"},{"key":"e_1_3_2_2_48_1","volume-title":"Proceedings of the sixth annual ACM\u2013SIAM symposium on Discrete algorithms (SODA\u201995)","author":"Grinberg Dennis"},{"key":"e_1_3_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.72"},{"key":"e_1_3_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/360825.360869"},{"key":"e_1_3_2_2_51_1","unstructured":"James H. Hester Daniel S. Hirschberg Shou-Hsuan Stephen Huang and C. K. Wong. 1986.  James H. Hester Daniel S. Hirschberg Shou-Hsuan Stephen Huang and C. K. Wong. 1986."},{"key":"e_1_3_2_2_52_1","doi-asserted-by":"crossref","unstructured":"Faster Construction of Optimal Binary Split Trees. Journal of Algorithms 7 3 (1986) 412\u2013424.  Faster Construction of Optimal Binary Split Trees. Journal of Algorithms 7 3 (1986) 412\u2013424.","DOI":"10.1016\/0196-6774(86)90031-3"},{"key":"e_1_3_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(77)80011-9"},{"key":"e_1_3_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1137\/0122024"},{"key":"e_1_3_2_2_55_1","unstructured":"T. C. Hu and Alan Curtiss Tucker. 1971.  T. C. Hu and Alan Curtiss Tucker. 1971."},{"key":"e_1_3_2_2_56_1","doi-asserted-by":"crossref","unstructured":"Optimal computer search trees and variable length alphabetic codes. Journal of Applied Mathematics 21 (1971) 514\u2013532.  Optimal computer search trees and variable length alphabetic codes. Journal of Applied Mathematics 21 (1971) 514\u2013532.","DOI":"10.1137\/0121057"},{"key":"e_1_3_2_2_57_1","unstructured":"Shou-Hsuan Stephen Huang and C. K. Wong. 1984.  Shou-Hsuan Stephen Huang and C. K. Wong. 1984."},{"key":"e_1_3_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00289143"},{"key":"e_1_3_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(84)90041-5"},{"key":"e_1_3_2_2_60_1","unstructured":"David A. Huffman. 1952.  David A. Huffman. 1952."},{"key":"e_1_3_2_2_61_1","volume-title":"Method for the Construction of Minimum-Redundancy Codes. In Proceedings of the I.R.E. 1098\u20131103","author":"A"},{"key":"e_1_3_2_2_62_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(76)90095-8"},{"key":"e_1_3_2_2_63_1","unstructured":"Ottar Johnsen. 1980.  Ottar Johnsen. 1980."},{"key":"e_1_3_2_2_64_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1980.1056158"},{"key":"e_1_3_2_2_65_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1077"},{"key":"e_1_3_2_2_66_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00565647"},{"key":"e_1_3_2_2_67_1","doi-asserted-by":"crossref","unstructured":"Richard M. Karp. 1961. Minimum-redundancy coding for the discrete noiseless channel. I.R.E. Transactions on Information Theory (1961) 27\u201338.  Richard M. Karp. 1961. Minimum-redundancy coding for the discrete noiseless channel. I.R.E. Transactions on Information Theory (1961) 27\u201338.","DOI":"10.1109\/TIT.1961.1057615"},{"key":"e_1_3_2_2_68_1","unstructured":"Gyula O. H. Katona. 1973.  Gyula O. H. Katona. 1973."},{"key":"e_1_3_2_2_69_1","volume-title":"A Survery of Combinatorial Theory","author":"Problems Combinatorial Search"},{"key":"e_1_3_2_2_70_1","doi-asserted-by":"publisher","DOI":"10.1137\/0602018"},{"key":"e_1_3_2_2_71_1","unstructured":"Donald E. Knuth. 1971.  Donald E. Knuth. 1971."},{"key":"e_1_3_2_2_72_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00264289"},{"key":"e_1_3_2_2_73_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(85)90036-7"},{"key":"e_1_3_2_2_74_1","unstructured":"S. Rao Kosaraju Teresa M. Przytycka and Ryan Borgstrom. 1999.  S. Rao Kosaraju Teresa M. Przytycka and Ryan Borgstrom. 1999."},{"key":"e_1_3_2_2_75_1","volume-title":"Algorithms and Data Structures: 6th International Workshop, WADS\u201999 Vancouver, Canada, August 11\u201314","author":"Optimal Split Tree Problem On","year":"1999"},{"key":"e_1_3_2_2_76_1","unstructured":"T. W. Lam and F. L. Yue. 2001.  T. W. Lam and F. L. Yue. 2001."},{"key":"e_1_3_2_2_77_1","doi-asserted-by":"crossref","unstructured":"Optimal edge ranking of trees in linear time. Algorithmica 30 1 (2001) 12\u201333.  Optimal edge ranking of trees in linear time. Algorithmica 30 1 (2001) 12\u201333.","DOI":"10.1007\/s004530010076"},{"key":"e_1_3_2_2_78_1","unstructured":"Jean-Luc Lambert. 1992.  Jean-Luc Lambert. 1992."},{"key":"e_1_3_2_2_79_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90089-X"},{"key":"e_1_3_2_2_80_1","unstructured":"Lawrence L. Larmore. 1987.  Lawrence L. Larmore. 1987."},{"key":"e_1_3_2_2_81_1","doi-asserted-by":"publisher","DOI":"10.1137\/0216070"},{"key":"e_1_3_2_2_82_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(85)90087-1"},{"key":"e_1_3_2_2_83_1","unstructured":"Nati Linial and Michael Saks. 1985.  Nati Linial and Michael Saks. 1985."},{"key":"e_1_3_2_2_84_1","doi-asserted-by":"crossref","unstructured":"Searching order structures. Journal of Algorithms 6 (1985) 86\u2013103.  Searching order structures. Journal of Algorithms 6 (1985) 86\u2013103.","DOI":"10.1016\/0196-6774(85)90020-3"},{"key":"e_1_3_2_2_85_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(87)90029-X"},{"key":"e_1_3_2_2_86_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.108260"},{"key":"e_1_3_2_2_87_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1993.1057"},{"key":"e_1_3_2_2_88_1","doi-asserted-by":"publisher","DOI":"10.1145\/828.322450"},{"key":"e_1_3_2_2_89_1","unstructured":"Soheil Mohajer Payam Pakzad and Ali Kakhbod. 2006.  Soheil Mohajer Payam Pakzad and Ali Kakhbod. 2006."},{"key":"e_1_3_2_2_90_1","volume-title":"Bounds on the Redundancy of Huffman Codes. In Information Theory Workshop (ITW \u201906)","author":"Tight"},{"key":"e_1_3_2_2_91_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1987.1057266"},{"key":"e_1_3_2_2_92_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11083-015-9347-y"},{"key":"e_1_3_2_2_93_1","volume-title":"Proceedings of 19th Symposium on Discrete Algorithms (SODA\u201908)","author":"Mozes Shay","year":"2008"},{"key":"e_1_3_2_2_94_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00320-9"},{"key":"e_1_3_2_2_95_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.86980"},{"key":"e_1_3_2_2_96_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.32"},{"key":"e_1_3_2_2_97_1","unstructured":"Yehoshua Perl. 1984.  Yehoshua Perl. 1984."},{"key":"e_1_3_2_2_98_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(84)90017-8"},{"key":"e_1_3_2_2_99_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022643204877"},{"key":"e_1_3_2_2_100_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.172.0101"},{"key":"e_1_3_2_2_101_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90014-8"},{"key":"e_1_3_2_2_102_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0955"},{"key":"e_1_3_2_2_103_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1948.tb01338.x"},{"key":"e_1_3_2_2_104_1","unstructured":"B. A. Sheil. 1978.  B. A. Sheil. 1978."},{"key":"e_1_3_2_2_105_1","doi-asserted-by":"publisher","DOI":"10.1145\/359642.359653"},{"key":"e_1_3_2_2_106_1","unstructured":"Dafna Sheinwald. 1992.  Dafna Sheinwald. 1992."},{"key":"e_1_3_2_2_107_1","volume-title":"Data Compression Conference (DCC\u201992)","author":"On"},{"key":"e_1_3_2_2_108_1","unstructured":"Cedric A. B. Smith. 1947.  Cedric A. B. Smith. 1947."},{"key":"e_1_3_2_2_109_1","doi-asserted-by":"crossref","unstructured":"The Counterfeit Coin Problem. The Mathematical Gazette 31 293 (1947) 31\u201339.  The Counterfeit Coin Problem. The Mathematical Gazette 31 293 (1947) 31\u201339.","DOI":"10.2307\/3608991"},{"key":"e_1_3_2_2_110_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300000080"},{"key":"e_1_3_2_2_111_1","doi-asserted-by":"publisher","DOI":"10.5555\/202497.202503"},{"key":"e_1_3_2_2_112_1","unstructured":"David A. Spuler. 1994.  David A. Spuler. 1994."},{"key":"e_1_3_2_2_113_1","unstructured":"Optimal Binary Trees With Two-Way Key Comparisons. Ph.D. Dissertation. James Cook University.  Optimal Binary Trees With Two-Way Key Comparisons. Ph.D. Dissertation. James Cook University."},{"key":"e_1_3_2_2_114_1","unstructured":"Jan van Leeuwen. 1987.  Jan van Leeuwen. 1987."},{"key":"e_1_3_2_2_115_1","unstructured":"On the construction of Huffman trees. In Third International Colloquium on Automata Languages and Programming (ICALP \u201987). 382\u2013410.  On the construction of Huffman trees. In Third International Colloquium on Automata Languages and Programming (ICALP \u201987). 382\u2013410."},{"key":"e_1_3_2_2_116_1","unstructured":"Jeffrey Scott Vitter. 1987.  Jeffrey Scott Vitter. 1987."},{"key":"e_1_3_2_2_117_1","doi-asserted-by":"publisher","DOI":"10.1145\/31846.42227"},{"key":"e_1_3_2_2_118_1","unstructured":"W. A. Walker and C. C. Gottlieb. 1972.  W. A. Walker and C. C. Gottlieb. 1972."},{"key":"e_1_3_2_2_119_1","unstructured":"A top-down algorithm for constructing nearly optimal lexicographical trees. Academic Press 303\u2013323.  A top-down algorithm for constructing nearly optimal lexicographical trees. Academic Press 303\u2013323."},{"key":"e_1_3_2_2_120_1","volume-title":"8th International Colloquium on Structural Information and Communication Complexity (SIROCCO). 337\u2013350","author":"Watkinson John"},{"key":"e_1_3_2_2_121_1","unstructured":"Raymond W. Yeung. 1991.  Raymond W. Yeung. 1991."}],"event":{"name":"STOC '17: Symposium on Theory of Computing","location":"Montreal Canada","acronym":"STOC '17","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3055399.3055422","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3055399.3055422","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:23:27Z","timestamp":1750206207000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3055399.3055422"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,19]]},"references-count":121,"alternative-id":["10.1145\/3055399.3055422","10.1145\/3055399"],"URL":"https:\/\/doi.org\/10.1145\/3055399.3055422","relation":{},"subject":[],"published":{"date-parts":[[2017,6,19]]},"assertion":[{"value":"2017-06-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}