{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,29]],"date-time":"2025-10-29T06:11:56Z","timestamp":1761718316975,"version":"3.40.4"},"publisher-location":"Berlin, Heidelberg","reference-count":51,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662439470"},{"type":"electronic","value":"9783662439487"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-43948-7_71","type":"book-chapter","created":{"date-parts":[[2014,6,11]],"date-time":"2014-06-11T16:10:36Z","timestamp":1402503036000},"page":"859-870","source":"Crossref","is-referenced-by-count":6,"title":["Fast Pseudorandomness for Independence and Load Balancing"],"prefix":"10.1007","author":[{"given":"Raghu","family":"Meka","sequence":"first","affiliation":[]},{"given":"Omer","family":"Reingold","sequence":"additional","affiliation":[]},{"given":"Guy N.","family":"Rothblum","sequence":"additional","affiliation":[]},{"given":"Ron D.","family":"Rothblum","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"5","key":"71_CR1","doi-asserted-by":"publisher","first-page":"667","DOI":"10.1145\/324133.324179","volume":"46","author":"N. Alon","year":"1999","unstructured":"Alon, N., Dietzfelbinger, M., Miltersen, P.B., Petrank, E., Tardos, G.: Linear hash functions. J. ACM\u00a046(5), 667\u2013683 (1999)","journal-title":"J. ACM"},{"issue":"3","key":"71_CR2","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1002\/rsa.3240030308","volume":"3","author":"N. Alon","year":"1992","unstructured":"Alon, N., Goldreich, O., H\u00e5stad, J., Peralta, R.: Simple construction of almost k-wise independent random variables. Random Struct. Algorithms\u00a03(3), 289\u2013304 (1992)","journal-title":"Random Struct. Algorithms"},{"key":"71_CR3","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1112\/blms\/22.6.583","volume":"22","author":"M. Ajtai","year":"1990","unstructured":"Ajtai, M., Iwaniec, H., Koml\u00f3s, J., Pintz, J., Szemer\u00e9di, E.: Construction of a thin set with small Fourier coefficients. Bulletin of the London Mathematical Society\u00a022, 583\u2013590 (1990)","journal-title":"Bulletin of the London Mathematical Society"},{"issue":"4","key":"71_CR4","doi-asserted-by":"publisher","first-page":"845","DOI":"10.1137\/S0097539705446950","volume":"36","author":"B. Applebaum","year":"2006","unstructured":"Applebaum, B., Ishai, Y., Kushilevitz, E.: Cryptography in NC0. SIAM J. Comput.\u00a036(4), 845\u2013888 (2006)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"71_CR5","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1016\/0020-0190(95)00032-8","volume":"54","author":"N. Alon","year":"1995","unstructured":"Alon, N., Mansour, Y.: Epsilon-discrepancy sets and their application for interpolation of sparse polynomials. Inf. Process. Lett.\u00a054(6), 337\u2013342 (1995)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"71_CR6","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/PL00009813","volume":"18","author":"Y. Azar","year":"1998","unstructured":"Azar, Y., Motwani, R., Naor, J.: Approximating probability distributions using small sample spaces. Combinatorica\u00a018(2), 151\u2013171 (1998)","journal-title":"Combinatorica"},{"key":"71_CR7","doi-asserted-by":"crossref","unstructured":"Andersson, A.: Faster deterministic sorting and searching in linear space. In: FOCS, pp. 135\u2013144 (1996)","DOI":"10.1109\/SFCS.1996.548472"},{"issue":"2","key":"71_CR8","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1002\/rsa.3240050203","volume":"5","author":"N. Alon","year":"1994","unstructured":"Alon, N., Roichman, Y.: Random Cayley graphs and expanders. Random Struct. Algorithms\u00a05(2), 271\u2013285 (1994)","journal-title":"Random Struct. Algorithms"},{"key":"71_CR9","doi-asserted-by":"publisher","first-page":"253","DOI":"10.4086\/toc.2013.v009a005","volume":"9","author":"A. Ben-Aroya","year":"2013","unstructured":"Ben-Aroya, A., Ta-Shma, A.: Constructing small-bias sets from algebraic-geometric codes. Theory of Computing\u00a09, 253\u2013272 (2013)","journal-title":"Theory of Computing"},{"key":"71_CR10","doi-asserted-by":"crossref","unstructured":"Babai, L., Fortnow, L., Levin, L.A., Szegedy, M.: Checking computations in polylogarithmic time. In: STOC, pp. 21\u201331 (1991)","DOI":"10.1145\/103418.103428"},{"issue":"4","key":"71_CR11","doi-asserted-by":"publisher","first-page":"889","DOI":"10.1137\/S0097539705446810","volume":"36","author":"E. Ben-Sasson","year":"2006","unstructured":"Ben-Sasson, E., Goldreich, O., Harsha, P., Sudan, M., Vadhan, S.P.: Robust PCPs of proximity, shorter PCPs, and applications to coding. SIAM J. Comput.\u00a036(4), 889\u2013974 (2006)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"71_CR12","doi-asserted-by":"publisher","first-page":"2464","DOI":"10.1137\/070712109","volume":"39","author":"A. Bogdanov","year":"2010","unstructured":"Bogdanov, A., Viola, E.: Pseudorandom bits for polynomials. SIAM J. Comput.\u00a039(6), 2464\u20132486 (2010)","journal-title":"SIAM J. Comput."},{"key":"71_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1007\/3-540-44683-4_24","volume-title":"Mathematical Foundations of Computer Science 2001","author":"M. Cryan","year":"2001","unstructured":"Cryan, M., Miltersen, P.B.: On pseudorandom generators in NC. In: Sgall, J., Pultr, A., Kolman, P. (eds.) MFCS 2001. LNCS, vol.\u00a02136, pp. 272\u2013284. Springer, Heidelberg (2001)"},{"issue":"3","key":"71_CR14","doi-asserted-by":"publisher","first-page":"1030","DOI":"10.1137\/120871626","volume":"42","author":"L. Elisa Celis","year":"2013","unstructured":"Elisa Celis, L.: Omer Reingold, Gil Segev, and Udi Wieder. Balls and bins: Smaller hash families and faster evaluation. SIAM J. Comput.\u00a042(3), 1030\u20131050 (2013)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"71_CR15","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/0022-0000(79)90044-8","volume":"18","author":"L. Carter","year":"1979","unstructured":"Carter, L., Wegman, M.N.: Universal classes of hash functions. J. Comput. Syst. Sci.\u00a018(2), 143\u2013154 (1979)","journal-title":"J. Comput. Syst. Sci."},{"key":"71_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/978-3-540-70575-8_32","volume-title":"Automata, Languages and Programming","author":"M. Dietzfelbinger","year":"2008","unstructured":"Dietzfelbinger, M., Pagh, R.: Succinct data structures for retrieval and approximate membership (extended abstract). In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol.\u00a05125, pp. 385\u2013396. Springer, Heidelberg (2008)"},{"key":"71_CR17","doi-asserted-by":"crossref","unstructured":"Dworkin, M.: Recommendations for Cipher Modes of Operation: Galois\/Counter Mode (GCM) and GMAC. NIST Special Publication 800-38D (2007)","DOI":"10.6028\/NIST.SP.800-38d"},{"issue":"1","key":"71_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1002\/(SICI)1098-2418(199808)13:1<1::AID-RSA1>3.0.CO;2-W","volume":"13","author":"G. Even","year":"1998","unstructured":"Even, G., Goldreich, O., Luby, M., Nisan, N., Velickovic, B.: Efficient approximation of product distributions. Random Struct. Algorithms\u00a013(1), 1\u201316 (1998)","journal-title":"Random Struct. Algorithms"},{"issue":"2","key":"71_CR19","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1145\/226643.226652","volume":"43","author":"U. Feige","year":"1996","unstructured":"Feige, U., Goldwasser, S., Lov\u00e1sz, L., Safra, S., Szegedy, M.: Interactive proofs and the hardness of approximating cliques. J. ACM\u00a043(2), 268\u2013292 (1996)","journal-title":"J. ACM"},{"key":"71_CR20","unstructured":"Gueron, S., Kounavis, M.E.: Intel\u00ae carry-less multiplication instruction and its usage for computing the GCM mode, rev 2.01 (2012)"},{"key":"71_CR21","doi-asserted-by":"crossref","unstructured":"Gopalan, P., Meka, R., Reingold, O., Trevisan, L., Vadhan, S.P.: Better pseudorandom generators from milder pseudorandom restrictions. In: FOCS, pp. 120\u2013129 (2012)","DOI":"10.1109\/FOCS.2012.77"},{"key":"71_CR22","doi-asserted-by":"crossref","unstructured":"Gutfreund, D., Viola, E.: Fooling parity tests with parity gates. In: Jansen, K., Khanna, S., Rolim, J.D.P., Ron, D. (eds.) RANDOM and APPROX 2004. LNCS, vol.\u00a03122, pp. 381\u2013392. Springer, Heidelberg (2004)","DOI":"10.1007\/978-3-540-27821-4_34"},{"key":"71_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"366","DOI":"10.1007\/BFb0028575","volume-title":"STACS 98","author":"T. Hagerup","year":"1998","unstructured":"Hagerup, T.: Sorting and searching on the word RAM. In: Meinel, C., Morvan, M. (eds.) STACS 1998. LNCS, vol.\u00a01373, pp. 366\u2013398. Springer, Heidelberg (1998)"},{"issue":"1","key":"71_CR24","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s00037-007-0238-5","volume":"17","author":"A. Healy","year":"2008","unstructured":"Healy, A.: Randomness-efficient sampling within nc1. Computational Complexity\u00a017(1), 3\u201337 (2008)","journal-title":"Computational Complexity"},{"issue":"1","key":"71_CR25","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1006\/jagm.2001.1171","volume":"41","author":"T. Hagerup","year":"2001","unstructured":"Hagerup, T., Miltersen, P.B., Pagh, R.: Deterministic dictionaries. J. Algorithms\u00a041(1), 69\u201385 (2001)","journal-title":"J. Algorithms"},{"key":"71_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"672","DOI":"10.1007\/11672142_55","volume-title":"STACS 2006","author":"A. Healy","year":"2006","unstructured":"Healy, A., Viola, E.: Constant-depth circuits for arithmetic in finite fields of characteristic two. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol.\u00a03884, pp. 672\u2013683. Springer, Heidelberg (2006)"},{"issue":"1","key":"71_CR27","doi-asserted-by":"publisher","first-page":"69","DOI":"10.4086\/toc.2009.v005a003","volume":"5","author":"S. Lovett","year":"2009","unstructured":"Lovett, S.: Unconditional pseudorandom generators for low degree polynomials. Theory of Computing\u00a05(1), 69\u201382 (2009)","journal-title":"Theory of Computing"},{"key":"71_CR28","doi-asserted-by":"crossref","unstructured":"Lacan, J., Roca, V., Peltotalo, J., Peltotalo, S.: Reed-Solomon Forward Error Correction (FEC) Schemes. RFC 5510 (Proposed Standard) (April 2009)","DOI":"10.17487\/rfc5510"},{"key":"71_CR29","doi-asserted-by":"crossref","unstructured":"Luby, M., Wigderson, A.: Pairwise independence and derandomization. Foundations and Trends in Theoretical Computer Science\u00a01(4) (2005)","DOI":"10.1561\/0400000009"},{"key":"71_CR30","unstructured":"Miltersen, P.B.: Cell probe complexity - a survey. In: 19th Conference on the Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 1999. Advances in Data Structures Workshop (1999)"},{"issue":"1","key":"71_CR31","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1002\/rsa.20112","volume":"29","author":"E. Mossel","year":"2006","unstructured":"Mossel, E., Shpilka, A., Trevisan, L.: On epsilon-biased generators in NC0. Random Struct. Algorithms\u00a029(1), 56\u201381 (2006)","journal-title":"Random Struct. Algorithms"},{"issue":"4","key":"71_CR32","doi-asserted-by":"publisher","first-page":"659","DOI":"10.1007\/s00493-004-0040-9","volume":"24","author":"R. Meshulam","year":"2004","unstructured":"Meshulam, R., Wigderson, A.: Expanders in group algebras. Combinatorica\u00a024(4), 659\u2013680 (2004)","journal-title":"Combinatorica"},{"key":"71_CR33","unstructured":"Naor, M.: Constructing Ramsey graphs from small probability spaces. IMB Research Report RJ(8810) (1992)"},{"issue":"4","key":"71_CR34","doi-asserted-by":"publisher","first-page":"838","DOI":"10.1137\/0222053","volume":"22","author":"J. Naor","year":"1993","unstructured":"Naor, J., Naor, M.: Small-bias probability spaces: Efficient constructions and applications. SIAM J. Comput.\u00a022(4), 838\u2013856 (1993)","journal-title":"SIAM J. Comput."},{"key":"71_CR35","unstructured":"National Institute of\u00a0Standards and Technology (NIST). Federal information processing standards publication (FIPS 197). Advanced Encryption Standard (AES) (2001)"},{"issue":"1","key":"71_CR36","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1137\/060658400","volume":"38","author":"A. Pagh","year":"2008","unstructured":"Pagh, A., Pagh, R.: Uniform hashing in constant time and optimal space. SIAM J. Comput.\u00a038(1), 85\u201396 (2008)","journal-title":"SIAM J. Comput."},{"key":"71_CR37","doi-asserted-by":"crossref","unstructured":"Pagh, A., Pagh, R., Ruzic, M.: Linear probing with constant independence. In: STOC, pp. 318\u2013327 (2007)","DOI":"10.1145\/1250790.1250839"},{"key":"71_CR38","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/3-540-61680-2_51","volume-title":"Algorithms - ESA \u201996","author":"R. Raman","year":"1996","unstructured":"Raman, R.: Priority queues: Small, monotone and trans-dichotomous. In: D\u00edaz, J. (ed.) ESA 1996. LNCS, vol.\u00a01136, pp. 121\u2013137. Springer, Heidelberg (1996)"},{"key":"71_CR39","unstructured":"Rao, A.: An exposition of Bourgain\u2019s 2-source extractor. Electronic Colloquium on Computational Complexity (ECCC)\u00a014(034) (2007)"},{"key":"71_CR40","doi-asserted-by":"crossref","unstructured":"Raz, R.: Extractors with weak random seeds. In: STOC, pp. 11\u201320 (2005)","DOI":"10.1145\/1060590.1060593"},{"key":"71_CR41","doi-asserted-by":"crossref","unstructured":"Roca, V., Cunche, M., Lacan, J., Bouabdallah, A., Matsuzono, K.: Simple Reed-Solomon Forward Error Correction (FEC) Scheme for FECFRAME. RFC 6865 (Proposed Standard) (February 2013)","DOI":"10.17487\/rfc6865"},{"key":"71_CR42","doi-asserted-by":"crossref","unstructured":"Reingold, O., Rothblum, R.D., Wieder, U.: Pseudorandom graphs in data structures (manuscript, 2014)","DOI":"10.1007\/978-3-662-43948-7_78"},{"issue":"2","key":"71_CR43","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1137\/0108018","volume":"8","author":"I.S. Reed","year":"1960","unstructured":"Reed, I.S., Solomon, G.: Polynomial codes over certain finite fields. Journal of the Society for Industrial and Applied Mathematics\u00a08(2), 300\u2013304 (1960)","journal-title":"Journal of the Society for Industrial and Applied Mathematics"},{"key":"71_CR44","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1017\/S0963548300000870","volume":"2","author":"A.A. Razborov","year":"1993","unstructured":"Razborov, A.A., Szemer\u00e9di, E., Wigderson, A.: Constructing small sets that are uniform in arithmetic progressions. Combinatorics, Probability & Computing\u00a02, 513\u2013518 (1993)","journal-title":"Combinatorics, Probability & Computing"},{"key":"71_CR45","unstructured":"Reingold, O., Vardi, S.: Tighter bounds for local computations (manuscript, 2014)"},{"issue":"4","key":"71_CR46","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1007\/s00037-009-0281-5","volume":"18","author":"A. Shpilka","year":"2009","unstructured":"Shpilka, A.: Constructions of low-degree and error-correcting epsilon-biased generators. Computational Complexity\u00a018(4), 495\u2013525 (2009)","journal-title":"Computational Complexity"},{"issue":"3","key":"71_CR47","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1137\/S0097539701386216","volume":"33","author":"A. Siegel","year":"2004","unstructured":"Siegel, A.: On universal classes of extremely random constant-time hash functions. SIAM J. Comput.\u00a033(3), 505\u2013543 (2004)","journal-title":"SIAM J. Comput."},{"key":"71_CR48","doi-asserted-by":"crossref","unstructured":"Thorup, M.: Simple tabulation, fast expanders, double tabulation, and high independence. In: FOCS (2013)","DOI":"10.1109\/FOCS.2013.18"},{"issue":"2","key":"71_CR49","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/s00037-009-0273-5","volume":"18","author":"E. Viola","year":"2009","unstructured":"Viola, E.: The sum of d small-bias generators fools polynomials of degree d. Computational Complexity\u00a018(2), 209\u2013217 (2009)","journal-title":"Computational Complexity"},{"issue":"3","key":"71_CR50","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/0022-0000(81)90033-7","volume":"22","author":"M.N. Wegman","year":"1981","unstructured":"Wegman, M.N., Carter, L.: New hash functions and their use in authentication and set equality. J. Comput. Syst. Sci.\u00a022(3), 265\u2013279 (1981)","journal-title":"J. Comput. Syst. Sci."},{"key":"71_CR51","unstructured":"Zuckerman, D.: Personal Communication"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-43948-7_71","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T09:31:03Z","timestamp":1746264663000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-43948-7_71"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662439470","9783662439487"],"references-count":51,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-43948-7_71","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}