{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T06:02:04Z","timestamp":1775282524227,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540609223","type":"print"},{"value":"9783540497233","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-60922-9_46","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T16:04:31Z","timestamp":1330272271000},"page":"567-580","source":"Crossref","is-referenced-by-count":30,"title":["Universal hashing and k-wise independent random variables via integer arithmetic without primes"],"prefix":"10.1007","author":[{"given":"Martin","family":"Dietzfelbinger","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"key":"46_CR1","doi-asserted-by":"crossref","unstructured":"K. Abrahamson. Time-space tradeoffs for branching programs contrasted with those for straight-line programs. In Proc. of the 27th IEEE FOCS, pp. 402\u2013409, 1986.","DOI":"10.1109\/SFCS.1986.58"},{"key":"46_CR2","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1002\/rsa.3240030308","volume":"3","author":"N. Alon","year":"1992","unstructured":"N. Alon, O. Goldreich, J.H\u00e5stad, and R. Peralta. Simple constructions of almost k-wise independent random variables. Random Structures and Algorithms, 3:289\u2013304, 1992.","journal-title":"Random Structures and Algorithms"},{"issue":"1","key":"46_CR3","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1002\/rsa.3240040109","volume":"4","author":"N. Alon","year":"1993","unstructured":"N. Alon, O. Goldreich, J. H\u00e5stad, and R. Peralta. Addendum to \u201csimple constructions of almost k-wise independent random variables\u201d. Random Structures and Algorithms, 4(1):119\u2013120, 1993.","journal-title":"Random Structures and Algorithms"},{"issue":"4","key":"46_CR4","doi-asserted-by":"publisher","first-page":"994","DOI":"10.1137\/0215070","volume":"15","author":"P. Beame","year":"1986","unstructured":"P. Beame, S.A.Cook, and H.J.Hoover. Log depth circuits for division and related problems. SIAM J. Comput., 15(4):994\u20131003, 1986.","journal-title":"SIAM J. Comput."},{"key":"46_CR5","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. of Complexity, 5:96\u2013106, 1989.","journal-title":"J. of Complexity"},{"key":"46_CR6","volume-title":"Introduction to Algorithms","author":"T. H. Cormen","year":"1990","unstructured":"T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. MIT Press, Cambridge, Mass., 1990."},{"key":"46_CR7","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. Comp. Syst. Sci., 18:143\u2013154, 1979.","journal-title":"J. Comp. Syst. Sci."},{"key":"46_CR8","doi-asserted-by":"crossref","unstructured":"M. Dietzfelbinger, J. Gil, Y. Matias, and N. Pippenger. Polynomial hash functions are reliable. In W. Kuich, editor, Proceedings of 19th ICALP, pp. 235\u2013246. Springer-Verlag, LNCS 623, 1992.","DOI":"10.1007\/3-540-55719-9_77"},{"key":"46_CR9","unstructured":"M. Dietzfelbinger, T. Hagerup, J. Katajainen, and M. Penttonen. A reliable randomized algorithm for the closest-pair problem. Research Report 513, Universit\u00e4t Dortmund, December 1993."},{"issue":"4","key":"46_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(4):738\u2013761, 1994.","journal-title":"SIAM J. Comput."},{"key":"46_CR11","volume-title":"Informatik. Festschrift zum 60. Geburtstag von G\u00fcnter Hotz, volume 1 of Teubner-Texte zur Informatik","author":"M. Dietzfelbinger","year":"1992","unstructured":"M. Dietzfelbinger and F. Meyer auf der Heide. Dynamic hashing in real time. In J. Buchmann, H. Ganzinger, and W. J. Paul, editors, Informatik. Festschrift zum 60. Geburtstag von G\u00fcnter Hotz, volume 1 of Teubner-Texte zur Informatik. B. G. Teubner, Stuttgart-Leipzig, 1992."},{"issue":"3","key":"46_CR12","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 O(1) worst case access time. J. Assoc. Comput. Mach., 31(3):538\u2013544, July 1984.","journal-title":"J. Assoc. Comput. Mach."},{"key":"46_CR13","volume-title":"An Introduction to the Theory of Numbers","author":"G. H. Hardy","year":"1994","unstructured":"G. H. Hardy, and E. M. Wright. An Introduction to the Theory of Numbers. Oxford Science Publications, Clarendon Press, Oxford, 1994."},{"issue":"4","key":"46_CR14","doi-asserted-by":"crossref","first-page":"762","DOI":"10.1145\/4221.4226","volume":"32","author":"R. M. Karp","year":"1985","unstructured":"R. M. Karp and A. Wigderson. A fast parallel algorithm for the maximal independent set problem. J. Assoc. Comput. Mach., 32(4):762\u2013773, 1985.","journal-title":"J. Assoc. Comput. Mach."},{"key":"46_CR15","doi-asserted-by":"crossref","unstructured":"N. Linial, M. Luby, M. Saks, and D. Zuckerman. Efficient construction of a small hitting set for combinatorial rectangles in high dimension. In Proc. of the 24th ACM STOC, pp. 258\u2013267 1993.","DOI":"10.1145\/167088.167166"},{"key":"46_CR16","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:1036\u20131053, 1986.","journal-title":"SIAM J. Comput."},{"key":"46_CR17","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-69672-5","volume-title":"Data Structures and Algorithms 1: Sorting and Searching","author":"K. Mehlhorn","year":"1984","unstructured":"K. Mehlhorn. Data Structures and Algorithms 1: Sorting and Searching. Springer-Verlag, Berlin, 1984."},{"key":"46_CR18","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/0304-3975(93)90257-T","volume":"107","author":"Y. Mansour","year":"1993","unstructured":"Y. Mansour, N. Nisan, and P. Tiwari. The computational complexity of universal hashing. Theoretical Computer Science, 107:121\u2013133, 1993.","journal-title":"Theoretical Computer Science"},{"key":"46_CR19","doi-asserted-by":"publisher","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 Informatica, 21:339\u2013374, 1984.","journal-title":"Acta Informatica"},{"key":"46_CR20","doi-asserted-by":"crossref","first-page":"573","DOI":"10.1016\/0196-6774(91)90034-V","volume":"12","author":"Y. Matias","year":"1991","unstructured":"Y. Matias and U. Vishkin. On parallel hashing and integer sorting. J. Algorithms, 12:573\u2013606, 1991.","journal-title":"J. Algorithms"},{"key":"46_CR21","doi-asserted-by":"crossref","unstructured":"N. Nisan. Pseudorandom generators for space-bounded computations. In Proc. of the 22nd ACM STOC, pp. 204\u2013212, 1990.","DOI":"10.1145\/100216.100242"},{"key":"46_CR22","doi-asserted-by":"crossref","unstructured":"J. Naor and M. Naor. Small-bias probabilitiy spaces: Efficient constructions and applications. In Proc. of the 22nd ACM STOC, pp. 213\u2013223, 1990.","DOI":"10.1145\/100216.100244"},{"key":"46_CR23","doi-asserted-by":"crossref","unstructured":"A. Siegel. On universal classes of fast high performance hash functions, their time-space tradeoff, and their applications. In Proc. of the 30th IEEE FOCS, pp. 20\u201325, 1989. Revised Version.","DOI":"10.1109\/SFCS.1989.63450"},{"key":"46_CR24","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1007\/BF02242355","volume":"7","author":"A. Sch\u00f6nhage","year":"1971","unstructured":"A. Sch\u00f6nhage and V. Strassen. Schnelle Multiplikation grosser Zahlen. Computing, 7:281\u2013292, 1971.","journal-title":"Computing"},{"key":"46_CR25","doi-asserted-by":"crossref","unstructured":"M. N. Wegman and J. L. Carter. New classes and applications of hash functions. In Proc. of 20th IEEE FOCS, pp. 175\u2013182, 1979.","DOI":"10.1109\/SFCS.1979.26"},{"key":"46_CR26","doi-asserted-by":"crossref","unstructured":"A. Wigderson and O. Goldreich. Tiny families of functions with random properties: A quality-size trade-off for hashing. In Proc. of 26th ACM STOC, pp. 574\u2013583, 1994.","DOI":"10.1145\/195058.195410"},{"key":"46_CR27","doi-asserted-by":"crossref","unstructured":"A. Wigderson. The amazing power of pairwise independence. In Proc. 26th ACM STOC, pp. 645\u2013647, 1994. (Invited lecture).","DOI":"10.1145\/195058.195420"}],"container-title":["Lecture Notes in Computer Science","STACS 96"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60922-9_46.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T16:02:37Z","timestamp":1605628957000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60922-9_46"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540609223","9783540497233"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/3-540-60922-9_46","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996]]}}}