Optimal bounds for the predecessor problem. (English) Zbl 1346.68099
Vitter, Jeffrey Scott (ed.) et al., Proceedings of the 31st annual ACM symposium on theory of computing, STOC 1999. Atlanta, GA, USA, May 1–4, 1999. New York, NY: ACM, Association for Computing Machinery (ISBN 1-58113-067-8). 295-304 (1999).
MSC:
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68Q05 | Models of computation (Turing machines, etc.) (MSC2010) |
| 68Q10 | Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) |
References:
| [1] | M. Ajtai, M. Fredman, and J. Komlfs. Hash functions for priority queues. Information and Control, 63:217-225, 1984. 10.1016/S0019-9958(84)80015-7 · Zbl 0591.68093 |
| [2] | Mikl6s Ajtai. A lower bound for finding predecessors in Yao’s cell probe model. Combinatorica, 8:235-247, 1988. · Zbl 0659.68030 |
| [3] | A. Andersson. Sublogarithmic seaching without multiplications. In 36th IEEE Annual Symposium on Foundations of Computer Science, pages 655-665, Milwaukee, Wl, 1995. · Zbl 0938.68602 |
| [4] | A. Andersson. Faster deterministic sorting and seaching in linear space. In 37th Annual IEEE Symposium on Foundations of Computer Science, pages 135-141, Burlington VT 1996. |
| [5] | A. Andersson, P. B. Miltersen, S. Riis, and M. Thorup. Static dictionaries on AC RAMs: query time O(x/logn/loglogn) is necessary and sufficient. In 37th Annual Symposium on Foundations of Computer Science, pages 441-450, Burlington, VT, October 1996. IEEE. |
| [6] | A. Andersson and M. Thorup. Exponential search trees for faster deterministic searching, sorting and priority queues in linear space. Manuscript. |
| [7] | A. Brodnik, P.B. Miltersen, and I. Munro. Trans-dichotomous algorithms without multiplications-some upper and lower bounds. In Proceedings of the 5th Work,hop on Algorithms and Data Structures, LNCS volume t272, pages 426-439, Halifax, NS, Canada, 1997. Springer-Verlag. · Zbl 1497.68553 |
| [8] | J. L. Carter and M. N. Wegman. Universal classes of hash functions. Journal of Computer and System Sciences, 18:143- 154, 1979. · Zbl 0412.68090 |
| [9] | A. Chakrabarti, B. Chazelle, B. Gum, and A. Lvov. A good neighbor is hard to find. In Proceedings of the Thirty First Annual ACM Symposium on Theory of Computing, Atlanta, GA, May 1999. 10.1145/301250.301325 · Zbl 1346.68078 |
| [10] | V. Chvfitat. Probabilistic methods in graph theory. Annals of Operations Research, 1:171-182, 1984. · Zbl 0673.05036 |
| [11] | M. Dietzfelbinger. Universal hashing and k-wise independent random variables via integer arithmetic without primes. In Proceedings of the 13th Annual Symposium on Theoretical Aspects of Computer Science, LNCS volume 1046, pages 569-580, Grenoble, France, February t996. Springer-Vedag. · Zbl 1379.68104 |
| [12] | M. Dietzfelbinger, J. Gil, Y. Matias, and N. Pippenger. Polynomial hash functions are reliable. In Automata, Languages, and Programming: 19th International Colloquium, LNCS volume 623, pages 235-246. Springer-Verlag. July 1992. · Zbl 1425.68098 |
| [13] | M. Dietzfelbingen A. Karlin, K. Mehthorn, E Meyer auf der Heide, H. Rohnert, and R Tarjan. Dynamic pertect hashing: Upper and lower bounds. SIAM Journal on Computing, 23(4):738-761, 1994. 10.1137/S0097539791194094 · Zbl 0820.68038 |
| [14] | M. Dietzfelbinger and E Meyer auf der Heide. A new universal class of hash functions and dynamic hashing in real time. In Automata, Languages, and Programming: 17th International Colloquium, LNCS volume 443, pages 6-17, Warwick University, England, July 1990. Springer-Verlag. · Zbl 0765.68026 |
| [15] | E Fich and P. B. Miltersen. Tables should be sorted (on random access machines). In Proceedings of the 4th Workxhop on Algorithms and Data Structures, LNCS volume 995, pages 163-174. Springer-Verlag, 1995. · Zbl 1502.68117 |
| [16] | M. Fredman, J. Kom!6s, and E. Szemerr:li. Storing a sparse table with O(1) worst case access time. Journal of the ACM, 31:538-544, 1984. 10.1145/828.1884 · Zbl 0629.68068 |
| [17] | M. Fredman and M. Saks. The cell probe complexity of dynamic data structures. In Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, pages 345- 354, Seattle, WA, May 1989. 10.1145/73007.73040 |
| [18] | M. Fredman and D. Willard. Surpassing the information theoretic bound with fusion trees. Journal of Computer and System Sciences, 47(3):424-436, 1993. 10.1016/0022-0000(93)90040-4 · Zbl 0795.68049 |
| [19] | Mauricio Karchmer and Avi Wigderson. Monotone circuits for connectivity require super-logarithmic depth. In Proceedings of the Twentieth Annual A CM Symposium on Theory of Computing, pages 539-550, Chicago, IL, May I988. 10.1145/62212.62265 · Zbl 0695.94021 |
| [20] | P. B. Miltersen. The bit probe complexity measure revisited. In Proceedings of the IOth Annual Symposium on Theoretical Aspects of Computer Science, LNCS volume 665, pages 662- 671, Wurzburg, Germany, February 1993. Springer-Verlag. · Zbl 0799.68048 |
| [21] | P. B. Miltersen. Lower bounds for Union-Split-Find related problems on random access machines. In Proceedings of the Twenty-Sixth Annual A CM Symposium on Theory of Computing, pages 625-634, Montrral, Qurbec, Canada, May 1994. 10.1145/195058.195415 · Zbl 1345.68118 |
| [22] | P.B. Miltersen, N. Nisar , S. Safra, and A. Wigderson. On data structures and asymmetric communication complexity. Journal of Computer and System Sciences, 57(1):37-49, t 998. 10.1006/jcss.1998.1577 · Zbl 0920.68042 |
| [23] | R. Raman. Priority queues: Small, monotone, and transdichotomous. In Proceedings of the 4th European Symposium on Algorithms, LNCS volume 1t36, pages 121-137. Springer-Verlag, 1996. · Zbl 1379.68108 |
| [24] | P. Van Erode Boas. Preserving order in a forest in less than logarithmic time and linear space. Information Processing Letters, 6:80-82, 1977. · Zbl 0364.68053 |
| [25] | E Van Erode Boas, R Kaas, and E. Zijlstra. Design and implementation of an efficient priority queue. Mathematical Systems Theory, 10:99-127, i977. · Zbl 0363.60104 |
| [26] | D. E. Willard. Log-logarithmic worst case range queries are possible in space O(n). Information Processing Letters, 17:81-84, 1983. · Zbl 0509.68106 |
| [27] | Bing Xiao. New bounds in cell probe model. PhD thesis, University of California, San Diego, 1992. |
| [28] | ^. C. Yao. Some complexity questions related to distributive computing. In Conference Record of the Eleventh Annual A CM Symposium on Theory of Computing, pages 209-213, Atlanta, GA, April-May 1979. 10.1145/800135.804414 |
| [29] | A. C. Yao. Should tables be sorted? Journal of the ACM, 28:615-628, July 198 t. 10.1145/322261.322274 · Zbl 0462.68079 |
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.
