Abstract
We provide new constructions of several fundamental pseudorandom objects. Loosely speaking, these constructions obtain exponential improvements in efficiency compared to previous constructions with comparable randomness complexity. Our measure of efficiency is the number of word operations, as captured by the well-established unit-cost word RAM model. Our main results are the following:
-
1
A family of (1/n)-almost logn-wise independent Boolean hash functions with O(logn) description length (or seed length) and O(loglogn) operations per evaluation.
Prior constructions with similar seed lengths required Θ(logn) operations.
-
2
ε-biased sequences for ε = 1/poly(n) with seed length O(logn loglogn) and O((loglogn)2) operations (to evaluate an output bit or a block of up to logn consecutive bits).
Prior constructions achieve O(logn) seed length, but require Θ(logn) operations. This construction implies pseudorandom generators with similar efficiency that fool classes such as low-degree polynomials and read-once CNFs.
-
3
Hash functions for placing n balls in n bins such that with all but probability 1/n the maximal load is O(logn/loglogn) (which is optimal), with seed-length O(logn loglogn) and O((loglogn)2) operations per evaluation.
The previously known construction with similar seed length required Θ(logn loglogn) operations. Indeed, our construction is an efficient instantiation of that construction, due to Celis, Reingold, Segev and Wieder (FOCS 2011).
These constructions are all simultaneously within loglogn factors of the optimal seed length, and within (loglogn)2 factors of the optimal computational efficiency.
The full version is available on the authors’ homepages.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Alon, N., Dietzfelbinger, M., Miltersen, P.B., Petrank, E., Tardos, G.: Linear hash functions. J. ACM 46(5), 667–683 (1999)
Alon, N., Goldreich, O., Håstad, J., Peralta, R.: Simple construction of almost k-wise independent random variables. Random Struct. Algorithms 3(3), 289–304 (1992)
Ajtai, M., Iwaniec, H., Komlós, J., Pintz, J., Szemerédi, E.: Construction of a thin set with small Fourier coefficients. Bulletin of the London Mathematical Society 22, 583–590 (1990)
Applebaum, B., Ishai, Y., Kushilevitz, E.: Cryptography in NC0. SIAM J. Comput. 36(4), 845–888 (2006)
Alon, N., Mansour, Y.: Epsilon-discrepancy sets and their application for interpolation of sparse polynomials. Inf. Process. Lett. 54(6), 337–342 (1995)
Azar, Y., Motwani, R., Naor, J.: Approximating probability distributions using small sample spaces. Combinatorica 18(2), 151–171 (1998)
Andersson, A.: Faster deterministic sorting and searching in linear space. In: FOCS, pp. 135–144 (1996)
Alon, N., Roichman, Y.: Random Cayley graphs and expanders. Random Struct. Algorithms 5(2), 271–285 (1994)
Ben-Aroya, A., Ta-Shma, A.: Constructing small-bias sets from algebraic-geometric codes. Theory of Computing 9, 253–272 (2013)
Babai, L., Fortnow, L., Levin, L.A., Szegedy, M.: Checking computations in polylogarithmic time. In: STOC, pp. 21–31 (1991)
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. 36(4), 889–974 (2006)
Bogdanov, A., Viola, E.: Pseudorandom bits for polynomials. SIAM J. Comput. 39(6), 2464–2486 (2010)
Cryan, M., Miltersen, P.B.: On pseudorandom generators in NC. In: Sgall, J., Pultr, A., Kolman, P. (eds.) MFCS 2001. LNCS, vol. 2136, pp. 272–284. Springer, Heidelberg (2001)
Elisa Celis, L.: Omer Reingold, Gil Segev, and Udi Wieder. Balls and bins: Smaller hash families and faster evaluation. SIAM J. Comput. 42(3), 1030–1050 (2013)
Carter, L., Wegman, M.N.: Universal classes of hash functions. J. Comput. Syst. Sci. 18(2), 143–154 (1979)
Dietzfelbinger, M., Pagh, R.: Succinct data structures for retrieval and approximate membership (extended abstract). In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol. 5125, pp. 385–396. Springer, Heidelberg (2008)
Dworkin, M.: Recommendations for Cipher Modes of Operation: Galois/Counter Mode (GCM) and GMAC. NIST Special Publication 800-38D (2007)
Even, G., Goldreich, O., Luby, M., Nisan, N., Velickovic, B.: Efficient approximation of product distributions. Random Struct. Algorithms 13(1), 1–16 (1998)
Feige, U., Goldwasser, S., Lovász, L., Safra, S., Szegedy, M.: Interactive proofs and the hardness of approximating cliques. J. ACM 43(2), 268–292 (1996)
Gueron, S., Kounavis, M.E.: Intel® carry-less multiplication instruction and its usage for computing the GCM mode, rev 2.01 (2012)
Gopalan, P., Meka, R., Reingold, O., Trevisan, L., Vadhan, S.P.: Better pseudorandom generators from milder pseudorandom restrictions. In: FOCS, pp. 120–129 (2012)
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. 3122, pp. 381–392. Springer, Heidelberg (2004)
Hagerup, T.: Sorting and searching on the word RAM. In: Meinel, C., Morvan, M. (eds.) STACS 1998. LNCS, vol. 1373, pp. 366–398. Springer, Heidelberg (1998)
Healy, A.: Randomness-efficient sampling within nc1. Computational Complexity 17(1), 3–37 (2008)
Hagerup, T., Miltersen, P.B., Pagh, R.: Deterministic dictionaries. J. Algorithms 41(1), 69–85 (2001)
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. 3884, pp. 672–683. Springer, Heidelberg (2006)
Lovett, S.: Unconditional pseudorandom generators for low degree polynomials. Theory of Computing 5(1), 69–82 (2009)
Lacan, J., Roca, V., Peltotalo, J., Peltotalo, S.: Reed-Solomon Forward Error Correction (FEC) Schemes. RFC 5510 (Proposed Standard) (April 2009)
Luby, M., Wigderson, A.: Pairwise independence and derandomization. Foundations and Trends in Theoretical Computer Science 1(4) (2005)
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)
Mossel, E., Shpilka, A., Trevisan, L.: On epsilon-biased generators in NC0. Random Struct. Algorithms 29(1), 56–81 (2006)
Meshulam, R., Wigderson, A.: Expanders in group algebras. Combinatorica 24(4), 659–680 (2004)
Naor, M.: Constructing Ramsey graphs from small probability spaces. IMB Research Report RJ(8810) (1992)
Naor, J., Naor, M.: Small-bias probability spaces: Efficient constructions and applications. SIAM J. Comput. 22(4), 838–856 (1993)
National Institute of Standards and Technology (NIST). Federal information processing standards publication (FIPS 197). Advanced Encryption Standard (AES) (2001)
Pagh, A., Pagh, R.: Uniform hashing in constant time and optimal space. SIAM J. Comput. 38(1), 85–96 (2008)
Pagh, A., Pagh, R., Ruzic, M.: Linear probing with constant independence. In: STOC, pp. 318–327 (2007)
Raman, R.: Priority queues: Small, monotone and trans-dichotomous. In: Díaz, J. (ed.) ESA 1996. LNCS, vol. 1136, pp. 121–137. Springer, Heidelberg (1996)
Rao, A.: An exposition of Bourgain’s 2-source extractor. Electronic Colloquium on Computational Complexity (ECCC) 14(034) (2007)
Raz, R.: Extractors with weak random seeds. In: STOC, pp. 11–20 (2005)
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)
Reingold, O., Rothblum, R.D., Wieder, U.: Pseudorandom graphs in data structures (manuscript, 2014)
Reed, I.S., Solomon, G.: Polynomial codes over certain finite fields. Journal of the Society for Industrial and Applied Mathematics 8(2), 300–304 (1960)
Razborov, A.A., Szemerédi, E., Wigderson, A.: Constructing small sets that are uniform in arithmetic progressions. Combinatorics, Probability & Computing 2, 513–518 (1993)
Reingold, O., Vardi, S.: Tighter bounds for local computations (manuscript, 2014)
Shpilka, A.: Constructions of low-degree and error-correcting epsilon-biased generators. Computational Complexity 18(4), 495–525 (2009)
Siegel, A.: On universal classes of extremely random constant-time hash functions. SIAM J. Comput. 33(3), 505–543 (2004)
Thorup, M.: Simple tabulation, fast expanders, double tabulation, and high independence. In: FOCS (2013)
Viola, E.: The sum of d small-bias generators fools polynomials of degree d. Computational Complexity 18(2), 209–217 (2009)
Wegman, M.N., Carter, L.: New hash functions and their use in authentication and set equality. J. Comput. Syst. Sci. 22(3), 265–279 (1981)
Zuckerman, D.: Personal Communication
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Meka, R., Reingold, O., Rothblum, G.N., Rothblum, R.D. (2014). Fast Pseudorandomness for Independence and Load Balancing. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds) Automata, Languages, and Programming. ICALP 2014. Lecture Notes in Computer Science, vol 8572. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-43948-7_71
Download citation
DOI: https://doi.org/10.1007/978-3-662-43948-7_71
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-43947-0
Online ISBN: 978-3-662-43948-7
eBook Packages: Computer ScienceComputer Science (R0)