Twenty (simple) questions. (English) Zbl 1370.68085
Hatami, Hamed (ed.) et al., Proceedings of the 49th annual ACM SIGACT symposium on theory of computing, STOC ’17, Montreal, QC, Canada, June 19–23, 2017. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-4528-6). 9-21 (2017).
MSC:
| 68P30 | Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) |
| 91A46 | Combinatorial games |
| 91A80 | Applications of game theory |
| 94A45 | Prefix, length-variable, comma-free codes |
Keywords:
binary decision tree; combinatorial search theory; information theory; redundancy; twenty-questions gameReferences:
| [1] | Julia Abrahams. 1997. |
| [2] | Code and parse trees for lossless source encoding. In Compression and Complexity of Sequences. 145-171. · Zbl 1055.94008 |
| [3] | Micah Adler and Bruce M. Maggs. 2001. Protocols for Asymmetric Communication Channels. J. Comput. System Sci. 63, 4 (2001), 573-596. 10.1006/jcss.2001.1779 · Zbl 1006.68008 |
| [4] | Rudolf Ahlswede and Ingo Wegener. 1987. |
| [5] | Search problems. John Wiley & Sons, Inc., New York. |
| [6] | Nir Ailon and Bernard Chazelle. 2005. |
| [7] | Lower bounds for linear degeneracy testing. J. ACM 52, 2 (2005), 151-171. 10.1145/1059513.1059515 · Zbl 1286.68172 |
| [8] | Richard Anderson, Sampath Kannan, Howard Karloff, and Richard E. Ladner. 2002. |
| [9] | Thresholds and optimal binary comparison search trees. Journal of Algorithms 44 (2002), 338-358. 10.1016/S0196-6774(02)00203-1 · Zbl 1032.68067 |
| [10] | Javad A. Aslam and Aditi Dhagat. 1991. Searching in the presence of linearly bounded errors. In Proceedings of the twenty-third annual ACM symposium on Theory of computing (STOC ’91). 486-493. 10.1145/103418.103469 |
| [11] | Harout Aydinian, Ferdinando Cicalese, and Christian Deppe (Eds.). 2013. |
| [12] | Information Theory, Combinatorics, and Search Theory. Springer-Verlag Berlin Heidelberg. · Zbl 1259.94005 |
| [13] | Michael B. Baer. 2007. Twenty (or so) Questions: D-ary Length-Bounded Prefix Coding. In IEEE International Symposium on Information Theory (ISIT 2007). 896- 900. |
| [14] | Yosi Ben-Asher, Eitan Farchi, and Ilan Newman. 1999. Optimal search in trees. SIAM J. Comput. 28, 6 (1999), 2090-2102. 10.1137/S009753979731858X · Zbl 0939.68022 |
| [15] | Michael Ben-Or. 1983. Lower bounds for algebraic computation trees. In Proceedings of the 15th ACM Symposium on Theory of Computing. 80-86. 10.1145/800061.808735 |
| [16] | Prosenjit Bose and Karim Douïeb. 2009. Efficient Construction of Near-Optimal Binary and Multiway Search Trees. In Algorithms and Data Structures (WADS 2009). 230-241. 10.1007/978-3-642-03367-4_21 · Zbl 1253.68102 |
| [17] | Renato M. Capocelli, Raffaele Giancarlo, and Indeer Jeet Taneja. 1986. Bounds on the Redundancy of Huffman Codes. IEEE Transactions on Information Theory IT-32, 6 (1986), 854-857. 10.1109/TIT.1986.1057239 · Zbl 0611.94006 |
| [18] | Jean Cardinal, John Iacono, and Aurélien Ooms. 2016. Solving k-SUM using few linear queries. In 24th Annual European Symposium on Algorithms (ESA 2016). LIPIcs, 25:1-25:17. · Zbl 1397.68093 |
| [19] | 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-82. · Zbl 1472.68044 |
| [20] | David Cohn, Les Atlas, and Richard Ladner. 1994. |
| [21] | Improving Generalization with Active Learning. Machine Learning 15 (1994), 201-221. 10.1023/A:1022673506211 |
| [22] | C. J. Colbourn, J. H. Dinitz, and D. R. Stinson. 1993. Applications of combinatorial designs to communications, cryptography, and networking. In Surveys in Combinatorics, 1993, K. Walker (Ed.). London Mathematical Society Lecture Note Series, Vol. 187. Cambridge University Press. · Zbl 0972.94052 |
| [23] | Thomas M. Cover and Joy A. Thomas. 2006. |
| [24] | Elements of information theory (2. ed.). Wiley. · Zbl 1140.94001 |
| [25] | Roberto De Prisco and Alfredo De Santis. 1993. On Binary Search Trees. Inform. Process. Lett. 45, 5 (1993), 249-253. 10.1016/0020-0190(93)90212-R · Zbl 0771.68042 |
| [26] | Aditi Dhagat, Peter Gács, and Peter Winkler. 1992. On Playing “Twenty Questions” with a Liar. In Proceedings of 3rd Symposium on Discrete Algorithms (SODA’92). 16-22. · Zbl 0818.90138 |
| [27] | Robert Dorfman. 1943. The Detection of Defective Members of Large Populations. The Annals of Mathematical Statistics 14, 4 (1943), 436-440. |
| [28] | Ding-Zhu Du and Frank K. Hwang. 1999. |
| [29] | Combinatorial Group Testing and Its Applications (2nd ed.). Series on Applied Mathematics, Vol. 12. World Scientific. · Zbl 0952.90001 |
| [30] | Dwight Duffus, Bill Sands, and Peter Winkler. 1990. |
| [31] | Maximal chains and antichains in Boolean lattices. SIAM Journal on Discrete Mathematics 3, 2 (1990), 197-205. Twenty (Simple) Questions STOC’17, June 2017, Montreal, Canada · Zbl 0704.06001 |
| [32] | Jeff Erickson. 1999. |
| [33] | Lower bounds for linear satisfiability problems. Chicago Journal of Theoretical Computer Science 8 (1999). · Zbl 0924.68001 |
| [34] | William Evans and David Kirkpatrick. 2004. Restructuring ordered binary trees. Journal of Algorithms 50, 2 (2004), 168-193. 10.1016/S0196-6774(03)00094-4 · Zbl 1067.68101 |
| [35] | Ester Ezra and Micha Sharir. 2016. The Decision Tree Complexity for k-SUM is at most Nearly Quadratic. Manuscript. (2016). |
| [36] | Newton Faller. 1973. An adaptive system for data compression. In Record of the 7th Asilomar Conference on Circuits, Systems, and Computers. 593-597. · Zbl 0304.68038 |
| [37] | Michael L. Fredman. 1976. How good is the information theory bound in sorting? Theoretical Computer Science 1, 4 (1976), 355-361. · Zbl 0327.68056 |
| [38] | Ari Freund. 2015. Improved Subquadratic 3SUM. Algorithmica (2015), 1-19. 10.1007/s00453-015-0079-6 · Zbl 1359.68130 |
| [39] | Robert G. Gallager. 1978. Variations on a Theme by Huffman. IEEE Transactions on Information Theory IT-24, 6 (1978), 668-674. 10.1109/TIT.1978.1055959 · Zbl 0399.94012 |
| [40] | Michael R. Garey. 1974. Optimal Binary Search Trees with Restricted Maximal Depth. SIAM J. Comput. 3, 2 (1974), 101-110. · Zbl 0288.68058 |
| [41] | Michael R. Garey and Ronald L. Graham. 1974. |
| [42] | Performance bounds on the splitting algorithm for binary testing. Acta Informatica 3 (1974), 347-355. 10.1007/BF00263588 · Zbl 0276.68023 |
| [43] | Adriano M. Garsia and Michelle L. Wachs. 1977. A new algorithm for minimum cost binary trees. SIAM J. Comput. 6, 4 (1977), 622-642. · Zbl 0366.68028 |
| [44] | Edgar N. Gilbert. 1971. |
| [45] | Codes based on inaccurate source probabilities. IEEE Transactions on Information Theory 17, 3 (1971), 304-314. 10.1109/TIT.1971.1054638 · Zbl 0222.94018 |
| [46] | E. N. Gilbert and E. F. Moore. 1959. |
| [47] | Variable-Length Binary Encodings. Bell System Technical Journal 38 (1959), 933-967. |
| [48] | Dennis Grinberg, Sivaramakrishnan Rajagopalan, Ramarathnam Venkatesan, and Vicor K. Wei. 1995. Splay Trees for Data Compression. In Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms (SODA’95). 522-530. · Zbl 0848.68023 |
| [49] | Allan Grønlund and Seth Pettie. 2014. Threesomes, Degenerates, and Love Triangles. In 55th Annual Symposium on Foundations of Computer Science (FOCS’14). 621-630. 10.1109/FOCS.2014.72 |
| [50] | L. H. Harper, T. H. Payne, J. E. Savage, and E. Straus. 1975. Sorting X+Y. Commun. ACM 18, 6 (1975), 347-349. 10.1145/360825.360869 · Zbl 0304.68047 |
| [51] | James H. Hester, Daniel S. Hirschberg, Shou-Hsuan Stephen Huang, and C. K. Wong. 1986. |
| [52] | Faster Construction of Optimal Binary Split Trees. Journal of Algorithms 7, 3 (1986), 412-424. · Zbl 0637.68070 |
| [53] | Yasuichi Horibe. 1977. An improved bound for weight-balanced tree. Information and Control 34, 2 (1977), 148-151. · Zbl 0359.94020 |
| [54] | T. C. Hu and K. C. Tan. 1972. Path Length of Binary Search Trees. SIAM J. Appl. Math. 22, 2 (1972), 225-234. · Zbl 0239.94009 |
| [55] | T. C. Hu and Alan Curtiss Tucker. 1971. |
| [56] | Optimal computer search trees and variable length alphabetic codes. Journal of Applied Mathematics 21 (1971), 514-532. · Zbl 0228.94002 |
| [57] | Shou-Hsuan Stephen Huang and C. K. Wong. 1984. |
| [58] | Generalized binary split trees. Acta Informatica 21, 1 (1984), 113-123. 10.1007/BF00289143 · Zbl 0541.68038 |
| [59] | Shou-Hsuan Stephen Huang and C. K. Wong. 1984. Optimal binary split trees. Journal of Algorithms 5, 1 (1984), 69-79. · Zbl 0536.68060 |
| [60] | David A. Huffman. 1952. |
| [61] | A Method for the Construction of Minimum-Redundancy Codes. In Proceedings of the I.R.E. 1098-1103. · Zbl 0516.73049 |
| [62] | Laurent Hyafil and Ronald L. Rivest. 1976. Constructing optimal binary decision trees is NP-complete. Inform. Process. Lett. 5, 1 (1976), 15-17. · Zbl 0333.68029 |
| [63] | Ottar Johnsen. 1980. |
| [64] | On the Redundancy of Binary Huffman Codes. IEEE Transactions on Information Theory IT-26, 2 (1980), 220-222. 10.1109/TIT.1980.1056158 · Zbl 0431.94025 |
| [65] | Jeff Kahn and Jeong Han Kim. 1995. Entropy and Sorting. J. Comput. System Sci. 51, 3 (1995), 390-399. 10.1006/jcss.1995.1077 · Zbl 1294.68069 |
| [66] | Jeff Kahn and Michael Saks. 1984. Balancing poset extensions. Order 1, 2 (1984), 113-126. · Zbl 0561.06004 |
| [67] | Richard M. Karp. 1961. Minimum-redundancy coding for the discrete noiseless channel. I.R.E. Transactions on Information Theory (1961), 27-38. · Zbl 0099.34402 |
| [68] | Gyula O. H. Katona. 1973. |
| [69] | Combinatorial Search Problems. In A Survery of Combinatorial Theory, J. N. Srivastava et al. (Ed.). North-Holland Publishing Company. · Zbl 0274.90022 |
| [70] | Daniel J. Kleitman and Michael E. Saks. 1981. Set orderings requiring costliest alphabetic binary trees. SIAM Journal on Algebraic Discrete Mathematics 2, 2 (1981), 142-146. · Zbl 0498.68038 |
| [71] | Donald E. Knuth. 1971. |
| [72] | Optimum binary search trees. Acta Informatica 1, 1 (1971), 14-25. 10.1007/BF00264289 · Zbl 0233.68010 |
| [73] | Donald E. Knuth. 1985. Dynamic Huffman coding. Journal of Algorithms 6 (1985), 163-180. 10.1016/0196-6774(85)90036-7 · Zbl 0606.94007 |
| [74] | S. Rao Kosaraju, Teresa M. Przytycka, and Ryan Borgstrom. 1999. |
| [75] | On an Optimal Split Tree Problem. In Algorithms and Data Structures: 6th International Workshop, WADS’99 Vancouver, Canada, August 11-14, 1999 Proceedings, Frank Dehne, Jörg-Rüdiger Sack, Arvind Gupta, and Roberto Tamassia (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 157-168. DOI:http://dx. · Zbl 1063.68575 |
| [76] | T. W. Lam and F. L. Yue. 2001. |
| [77] | Optimal edge ranking of trees in linear time. Algorithmica 30, 1 (2001), 12-33. · Zbl 0984.68200 |
| [78] | Jean-Luc Lambert. 1992. |
| [79] | Sorting the sums (x i + y j ) in O (n 2 ) comparisons. Theoretical Computer Science 103, 1 (1992), 137-141. 10.1016/0304-3975(92)90089-X · Zbl 0753.68032 |
| [80] | Lawrence L. Larmore. 1987. |
| [81] | Height-restricted optimal binary trees. SIAM J. Comput. 16 (1987), 1115-1123. 10.1137/0216070 · Zbl 0654.68076 |
| [82] | Nati Linial and Michael Saks. 1985. Every poset has a central element. Journal of Combinatorial Theory 40 (1985), 195-210. · Zbl 0582.06002 |
| [83] | Nati Linial and Michael Saks. 1985. |
| [84] | Searching order structures. Journal of Algorithms 6 (1985), 86-103. · Zbl 0578.68050 |
| [85] | Zbigniew Lonc and Ivan Rival. 1987. Chains, Antichains, and Fibres. Journal of Combinatorial Theory, Series A 44 (1987), 207-228. 10.1016/0097-3165(87)90029-X · Zbl 0637.06001 |
| [86] | Dietrich Manstetten. 1992. Tight Bounds on the Redundancy of Huffman Codes. IEEE Transactions on Information Theory IT-38, 1 (1992), 144-151. 10.1109/18.108260 · Zbl 0745.94011 |
| [87] | S. Meiser. 1993. Point location in arrangements of hyperplanes. Information and Computation 106, 2 (1993), 286-303. 10.1006/inco.1993.1057 · Zbl 0781.68121 |
| [88] | Friedhelm Meyer auf der Heide. 1984. A polynomial linear search algorithm for the n-dimensional knapsack problem. J. ACM 31 (1984), 668-676. 10.1145/828.322450 · Zbl 0631.68037 |
| [89] | Soheil Mohajer, Payam Pakzad, and Ali Kakhbod. 2006. |
| [90] | Tight Bounds on the Redundancy of Huffman Codes. In Information Theory Workshop (ITW ’06). 131- 135. |
| [91] | Bruce L. Montgomery and Julia Abrahams. 1987. On the Redundancy of Optimal Binary Prefix-Condition Codes for Finite and Infinite Sources. IEEE Transactions on Information Theory IT-33, 1 (1987), 156-160. 10.1109/TIT.1987.1057266 · Zbl 0625.94010 |
| [92] | Shay Moran and Amir Yehudayoff. 2016. A note on average-case sorting. Order 33, 1 (2016), 23-28. · Zbl 1341.68036 |
| [93] | Shay Mozes, Krzysztof Onak, and Oren Weimann. 2008. Finding an optimal tree searching strategy in linear time. In Proceedings of 19th Symposium on Discrete Algorithms (SODA’08). 1096-1105. · Zbl 1192.68242 |
| [94] | S. V. Nagaraj. 1997. Optimal binary search trees. Theoretical Computer Science 188, 1-2 (1997), 1-44. 10.1016/S0304-3975(96)00320-9 · Zbl 0893.68045 |
| [95] | Narao Nakatsu. 1991. Bounds on the Redundancy of Binary Alphabetical Codes. IEEE Transactions on Information Theory IT-37, 4 (1991), 1225-1229. 10.1109/18.86980 · Zbl 0733.94010 |
| [96] | Krzysztof Onak and Paweł Parys. 2006. Generalization of Binary Search: Searching in Trees and Forest-Like Partial Orders. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings. 379-388. DOI:http://dx. 10.1109/FOCS.2006.32 |
| [97] | Yehoshua Perl. 1984. |
| [98] | Optimum split trees. Journal of Algorithms 5, 3 (1984), 367-374. 10.1016/0196-6774(84)90017-8 · Zbl 0546.68042 |
| [99] | J. Ross Quinlan. 1986. Induction of Decision Trees. Machine Learning 1 (1986), 81-106. 10.1023/A:1022643204877 |
| [100] | Jorma Rissanen. 1973. Bounds for weight balanced trees. IBM Journal of Research and Development 17 (1973), 101-105. 10.1147/rd.172.0101 · Zbl 0257.68031 |
| [101] | Ronald L. Rivest, Albert R. Meyer, Daniel J. Kleitman, Karl Winklmann, and Joel Spencer. 1980. Coping with errors in binary search procedures. J. Comput. System Sci. 20 (1980), 396-404. · Zbl 0443.68043 |
| [102] | Baruch Schieber. 1998. Computing a Minimum Weight k-Link Path in Graphs with the Concave Monge Property. Journal of Algorithms 29 (1998), 204-222. 10.1006/jagm.1998.0955 · Zbl 0916.68066 |
| [103] | Claude Elwood Shannon. 1948. A Mathematical Theory of Communication. Bell System Technical Journal 27 (1948), 379-423. · Zbl 1154.94303 |
| [104] | B. A. Sheil. 1978. |
| [105] | Median split trees: a fast lookup technique for frequently occuring keys. Commun. ACM 21, 11 (1978), 947-958. 10.1145/359642.359653 · Zbl 0386.68060 |
| [106] | Dafna Sheinwald. 1992. |
| [107] | On binary alphabetical codes. In Data Compression Conference (DCC’92). 112-121. |
| [108] | Cedric A. B. Smith. 1947. |
| [109] | The Counterfeit Coin Problem. The Mathematical Gazette 31, 293 (1947), 31-39. |
| [110] | Joel Spencer and Peter Winkler. 1992. Three thresholds for a liar. Combinatorics, Probability and Computing 1, 1 (1992), 81-93. · Zbl 0801.90127 |
| [111] | David Spuler. 1994. Optimal search trees using two-way key comparisons. Acta Informatica 31 (1994), 729-740. · Zbl 0820.68040 |
| [112] | David A. Spuler. 1994. |
| [113] | Optimal Binary Trees With Two-Way Key Comparisons. Ph.D. Dissertation. James Cook University. |
| [114] | Jan van Leeuwen. 1987. |
| [115] | On the construction of Huffman trees. In Third International Colloquium on Automata, Languages and Programming (ICALP ’87). 382-410. · Zbl 0358.68065 |
| [116] | Jeffrey Scott Vitter. 1987. |
| [117] | Design and analysis of dynamic Huffman codes. J. ACM 34, 4 (1987), 825-845. 10.1145/31846.42227 · Zbl 0637.94002 |
| [118] | W. A. Walker and C. C. Gottlieb. 1972. |
| [119] | A top-down algorithm for constructing nearly optimal lexicographical trees. Academic Press, 303-323. · Zbl 0246.68005 |
| [120] | John Watkinson, Micah Adler, and Faith E. Fich. 2001. New Protocols for Asymmetric Communication Channels. In 8th International Colloquium on Structural Information and Communication Complexity (SIROCCO). 337-350. |
| [121] | Raymond W. Yeung. 1991. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
