{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T04:19:38Z","timestamp":1742617178910,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540614401"},{"type":"electronic","value":"9783540685807"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-61440-0_149","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T21:38:17Z","timestamp":1330292297000},"page":"442-453","source":"Crossref","is-referenced-by-count":9,"title":["Lower bounds for static dictionaries on RAMs with bit operations but no multiplication"],"prefix":"10.1007","author":[{"given":"Peter Bro","family":"Miltersen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,2]]},"reference":[{"key":"37_CR1","doi-asserted-by":"crossref","unstructured":"A. Andersson. Sublogarithmic searching without multiplications. In Proc. FOCS, 1995.","DOI":"10.1109\/SFCS.1995.492667"},{"key":"37_CR2","doi-asserted-by":"crossref","unstructured":"A. Andersson, T. Hagerup, S. Nilsson, and R. Raman. Sorting in linear time? In Proc. 27th ACM Symposium on Theory of Computing (STOC), pages 427\u2013436, 1995.","DOI":"10.1145\/225058.225173"},{"key":"37_CR3","doi-asserted-by":"crossref","unstructured":"A. Andersson, P.B. Miltersen, S. Riis, and M. Thorup. Static Dictionaries on AC0 RAMs: Query time \u221alog n\/ log log n is sufficient and necessary. Manuscript, 1996.","DOI":"10.7146\/brics.v4i14.21678"},{"key":"37_CR4","doi-asserted-by":"crossref","unstructured":"A.M. Ben-Amram and Z. Galil. When can we sort in o(n log n) time? In Proc. 34th IEEE Symposium on Foundations of Computer Science (FOCS), pages 538\u2013546, 1993.","DOI":"10.1109\/SFCS.1993.366833"},{"key":"37_CR5","doi-asserted-by":"crossref","unstructured":"N.H. Bshouty. Lower bounds for the complexity of functions in a realistic RAM model. In Proc. Israel Symposium on the Theory of Computing and Systems, pages 12\u201323, 1992.","DOI":"10.1007\/BFb0035162"},{"key":"37_CR6","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/0022-0000(79)90044-8","volume":"18","author":"J.L. Carter","year":"1979","unstructured":"J.L. Carter and M.N. Wegman. Universal classes of hash functions. J. Comput. Syst. Sci., 18:143\u2013154, 1979.","journal-title":"J. Comput. Syst. Sci."},{"key":"37_CR7","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1137\/0217026","volume":"17","author":"B. Chazelle","year":"1988","unstructured":"B. Chazelle. A functional approach to data structures and its use in multidimensional searching. SIAM J. Comput., 17:427\u2013462, 1988.","journal-title":"SIAM J. Comput."},{"key":"37_CR8","doi-asserted-by":"crossref","unstructured":"P.F. Dietz. Optimal algorithms for list indexing and subset rank. In Proc. First Workshop on Algorithms and Data Structures (WADS), pages 39\u201346, 1989.","DOI":"10.1007\/3-540-51542-9_5"},{"key":"37_CR9","unstructured":"M. Dietzfelbinger, T. Hagerup, J. Katajainen, and M. Penttonen. A reliable randomized algorithm for the closest-pair problem. Technical Report 513, Fachbereich Informatik, Universit\u00e4t Dortmund, 1993."},{"key":"37_CR10","doi-asserted-by":"publisher","first-page":"738","DOI":"10.1137\/S0097539791194094","volume":"23","author":"M. Dietzfelbinger","year":"1994","unstructured":"M. Dietzfelbinger, A. Karlin, K. Mehlhorn, F. Meyer Auf Der Heide, H. Rohnert, and R.E. Tarjan. Dynamic perfect hashing: Upper and lower bounds. SIAM J. Comput., 23:738\u2013761, 1994.","journal-title":"SIAM J. Comput."},{"key":"37_CR11","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/BF01683268","volume":"10","author":"P. Emde Boas van","year":"1977","unstructured":"P. van Emde Boas, R. Kaas, and E. Zijlstra. Design and implementation of an efficient priority queue. Mathematical Systems Theory, 10:99\u2013127, 1977.","journal-title":"Mathematical Systems Theory"},{"key":"37_CR12","doi-asserted-by":"crossref","unstructured":"F. Fich and P.B. Miltersen. Tables should be sorted (on random access machines). In Proc. 4th International Workshop on Algorithms and Data Structures (WADS), pages 482\u2013493, 1995.","DOI":"10.1007\/3-540-60220-8_87"},{"key":"37_CR13","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1145\/828.1884","volume":"31","author":"M.L. Fredman","year":"1984","unstructured":"M.L. Fredman, J. Koml\u00f3s, and E. Szemer\u00e9di. Storing a sparse table with 0(1) worst case access time. J. Ass. Comp. Mach., 31:538\u2013544, 1984.","journal-title":"J. Ass. Comp. Mach."},{"key":"37_CR14","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1016\/0022-0000(93)90040-4","volume":"47","author":"M.L. Fredman","year":"1993","unstructured":"M.L. Fredman and D.E. Willard. Surpassing the information theoretic bound with fusion trees. Journal of Computer and System Sciences, 47:424\u2013436, 1993.","journal-title":"Journal of Computer and System Sciences"},{"key":"37_CR15","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/0022-0000(85)90014-5","volume":"30","author":"H. N. Gabow","year":"1985","unstructured":"H. N. Gabow and R. E. Tarjan. A linear-time algorithm for a special case of disjoint set union. Journal of Computer and Systems Sciences, 30:209\u2013221, 1985.","journal-title":"Journal of Computer and Systems Sciences"},{"key":"37_CR16","unstructured":"M. Thorup. On RAM priority queues. In Proceedings of the 7th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 59\u201367, 1996."},{"key":"37_CR17","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1145\/322261.322274","volume":"28","author":"A.C. Yao","year":"1981","unstructured":"A.C. Yao. Should tables be sorted? J. Ass. Comp. Mach., 28:615\u2013628, 1981.","journal-title":"J. Ass. Comp. Mach."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-61440-0_149.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T23:18:42Z","timestamp":1742599122000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-61440-0_149"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540614401","9783540685807"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-61440-0_149","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}