{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T09:30:49Z","timestamp":1775899849708,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540557197","type":"print"},{"value":"9783540472780","type":"electronic"}],"license":[{"start":{"date-parts":[[1992,1,1]],"date-time":"1992-01-01T00:00:00Z","timestamp":694224000000},"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":[],"published-print":{"date-parts":[[1992]]},"DOI":"10.1007\/3-540-55719-9_77","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T10:34:11Z","timestamp":1330252451000},"page":"235-246","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":43,"title":["Polynomial hash functions are reliable"],"prefix":"10.1007","author":[{"given":"M.","family":"Dietzfelbinger","sequence":"first","affiliation":[]},{"given":"J.","family":"Gil","sequence":"additional","affiliation":[]},{"given":"Y.","family":"Matias","sequence":"additional","affiliation":[]},{"given":"N.","family":"Pippenger","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,2]]},"reference":[{"key":"19_CR1","doi-asserted-by":"publisher","first-page":"567","DOI":"10.1016\/0196-6774(86)90019-2","volume":"7","author":"N. Alon","year":"1986","unstructured":"N. Alon, L. Babai, and A. Itai. A fast and simple randomized parallel algorithm for the maximal independent set problem. J. of Alg., 7:567\u2013583, 1986.","journal-title":"J. of Alg."},{"key":"19_CR2","first-page":"143","volume":"18","author":"L. J. Carter","year":"1979","unstructured":"L. J. Carter and M. N. Wegman. Universal classes of hash functions. JCSS, 18:143\u2013154, 1979.","journal-title":"JCSS"},{"key":"19_CR3","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1016\/0885-064X(89)90015-0","volume":"5","author":"B. Chor","year":"1989","unstructured":"B. Chor and O. Goldreich. On the power of two-point based sampling. J. Complexity, 5:96\u2013106, 1989.","journal-title":"J. Complexity"},{"key":"19_CR4","unstructured":"M. Dietzfelbinger, A. R. Karlin, K. Mehlhorn, F. Meyer auf der Heide, H. Rohnert, and R. E. Tarian. Dynamic perfect hashing: Upper and lower bounds. Technical Report 70, Universit\u00e4t Paderborn, Gesamthochschule, Jan. 1991. Revised Version of the paper of the same title that appeared in FOCS '88, pp. 524\u2013531."},{"key":"19_CR5","doi-asserted-by":"crossref","unstructured":"M. Dietzfelbinger and F. Meyer auf der Heide. A new universal class of hash functions and dynamic hashing in real time. In ICALP '90 (LNCS 443), pp. 6\u201319, July 1990.","DOI":"10.1007\/BFb0032018"},{"issue":"3","key":"19_CR6","doi-asserted-by":"publisher","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 O(1) worst case access time. J. ACM, 31(3):538\u2013544, July 1984.","journal-title":"J. ACM"},{"key":"19_CR7","unstructured":"J. Gil and Y. Matias. Fast hashing on a PRAM-designing by expectation. In SODA '91, pp. 271\u2013280, Jan. 1991."},{"key":"19_CR8","doi-asserted-by":"crossref","unstructured":"J. Gil, Y. Matias, and U. Vishkin. Towards a theory of nearly constant time parallel algorithms. In FOCS '91, pp. 698\u2013710.","DOI":"10.1109\/SFCS.1991.185438"},{"issue":"1","key":"19_CR9","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/0020-0190(86)90041-4","volume":"22","author":"C. T. M. Jacobs","year":"1986","unstructured":"C. T. M. Jacobs and P. van Emde Boas. Two results on tables. IPL, 22(1):43\u201348, 1986.","journal-title":"IPL"},{"key":"19_CR10","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1214\/aop\/1176996762","volume":"2","author":"A. Joffe","year":"1974","unstructured":"A. Joffe. On a set of almost deterministic k-independent random variables. The Annals of Prob., 2:161\u2013162, 1974.","journal-title":"The Annals of Prob."},{"key":"19_CR11","doi-asserted-by":"crossref","unstructured":"A. R. Karlin and E. Upfal. Parallel hashing-an efficient implementation of shared memory. In STOC '86, pp. 160\u2013168.","DOI":"10.1145\/12130.12146"},{"key":"19_CR12","unstructured":"D. E. Knuth. Sorting and Searching, volume 3 of The Art of Computer Programming."},{"key":"19_CR13","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0304-3975(90)90192-K","volume":"71","author":"C. P. Kruskal","year":"1990","unstructured":"C. P. Kruskal. L. Rudolph, and M. Snir. A complexity theory of efficient parallel algorithms. TCS, 71:95\u2013132, 1990.","journal-title":"TCS"},{"issue":"4","key":"19_CR14","doi-asserted-by":"publisher","first-page":"1036","DOI":"10.1137\/0215074","volume":"15","author":"M. Luby","year":"1986","unstructured":"M. Luby. A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput., 15(4):1036\u20131053, 1986.","journal-title":"SIAM J. Comput."},{"key":"19_CR15","unstructured":"H. G. Mairson. The program complexity of searching a table. In FOCS '83, pp. 40\u201375."},{"key":"19_CR16","doi-asserted-by":"crossref","unstructured":"G. Markowsky, L. J. Carter, and M. N. Wegman. Analysis of a universal class of hash functions. In MFCS '78, pp. 345\u2013354, 1978.","DOI":"10.1007\/3-540-08921-7_82"},{"key":"19_CR17","doi-asserted-by":"crossref","unstructured":"K. Mehlhorn. On the program size of perfect and universal hash functions. In FOCS '82, pp. 170\u2013175.","DOI":"10.1109\/SFCS.1982.80"},{"key":"19_CR18","volume-title":"Data Structures and Algorithms","author":"K. Mehlhorn","year":"1984","unstructured":"K. Mehlhorn. Data Structures and Algorithms. Springer-Verlag, Berlin Heidelberg, 1984."},{"key":"19_CR19","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1007\/BF00264615","volume":"21","author":"K. Mehlhorn","year":"1984","unstructured":"K. Mehlhorn and U. Vishkin. Randomized and deterministic simulations of PRAMs by parallel machines with restricted granularity of parallel memories. Acta Inf., 21:339\u2013374, 1984.","journal-title":"Acta Inf."},{"key":"19_CR20","doi-asserted-by":"crossref","unstructured":"N. Nisan. Pseudorandom generators for space-bounded computations. In STOC '90, pp. 204\u2013212.","DOI":"10.1145\/100216.100242"},{"issue":"9","key":"19_CR21","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1145\/63500.63521","volume":"14","author":"M. V. Ramakrishna","year":"1989","unstructured":"M. V. Ramakrishna and P.-A. Larson. File organization using composite perfect hashing. ACM Trans. Database Syst., 14(9);231\u2013263. 1989.","journal-title":"ACM Trans. Database Syst."},{"key":"19_CR22","doi-asserted-by":"crossref","unstructured":"A. G. Ranade. How to emulate shared memory. In FOCS '87, pp. 185\u2013194.","DOI":"10.1109\/SFCS.1987.32"},{"key":"19_CR23","doi-asserted-by":"crossref","unstructured":"A. G. Ranade, S. N. Bhatt, and S. L. Johnsson. The fluent abstract machine. In Proc. of the 5th MIT Conference on Advanced Research in VLSI, pp. 71\u201393, 1988.","DOI":"10.21236\/ADA327476"},{"issue":"5","key":"19_CR24","doi-asserted-by":"publisher","first-page":"775","DOI":"10.1137\/0219054","volume":"19","author":"J. P. Schmidt","year":"1990","unstructured":"J. P. Schmidt and A. Siegel. The spatial complexity of oblivious k-probe hash functions. SIAM J. Comput., 19(5):775\u2013786, 1990.","journal-title":"SIAM J. Comput."},{"key":"19_CR25","unstructured":"A. Siegel. On universal classes of fast high performance hash functions, their time-space tradeoff, and their applications. In FOCS '89, pp. 20\u201325."},{"key":"19_CR26","doi-asserted-by":"crossref","unstructured":"C. Slot and P. van Emde Boas. On tape versus core; an application of space efficient hash functions to the invariance of space. In STOC '84, pp. 391\u2013400.","DOI":"10.1145\/800057.808705"},{"key":"19_CR27","doi-asserted-by":"crossref","unstructured":"M. N. Wegman and L. J. Carter. New classes and applications of hash functions. In FOCS '79, pp. 175\u2013182.","DOI":"10.1109\/SFCS.1979.26"},{"key":"19_CR28","first-page":"265","volume":"22","author":"M. N. Wegman","year":"1981","unstructured":"M. N. Wegman and L. J. Carter. New hash functions and their use in authentication and set equality. JCSS, 22:265\u2013279, 1981.","journal-title":"JCSS"},{"issue":"3","key":"19_CR29","doi-asserted-by":"publisher","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. ACM, 28(3);615\u2013628, July 1981.","journal-title":"J. ACM"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-55719-9_77","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T21:41:56Z","timestamp":1742593316000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-55719-9_77"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1992]]},"ISBN":["9783540557197","9783540472780"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/3-540-55719-9_77","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992]]},"assertion":[{"value":"2 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}