Pseudorandom generators for low degree polynomials

ABSTRACT

We investigate constructions of pseudorandom generators that fool polynomial tests of degree d in m variables over finite fields F. Our main construction gives a generator with seed length O(d⁴ log m (1 + log(d ⁄ ε) ⁄ log log m) + log |F|) bits that achieves arbitrarily small bias ε and works whenever |F| is at least polynomial in d, log m, and 1⁄ε. We also present an alternate construction that uses a seed that can be described by O(c²d⁸m^6⁄(c-2) log(d⁄ε) + log |F|) bits (more precisely, O(c²d⁸m^6⁄(c-2)) field elements, each chosen from a set of size poly(cd⁄ε), plus two field elements ranging over all of F), works whenever |F| is at least polynomial in c, d, and 1⁄ε, and has the property that every element of the output is a function of at most c field elements in the input. Both generators are computable by small arithmetic circuits. The main tool used in the construction is a reduction that allows us to transform any "dense" hitting set generator for polynomials into a pseudorandom generator.

REFERENCES

• 1: N. Alon, O. Goldreich, J. Hastad, and R. Peralta. Simple constructions of almost k-wise independent random variables. In Proceedings of the 31st IEEE Symposium on Foundations of Computer Science, pages 544--553, 1990.
• 2: Alexander E. Andreev , Andrea E. F. Clementi , José D. P. Rolim, A new general derandomization method, Journal of the ACM (JACM), v.45 n.1, p.179-213, Jan. 1998 [doi>10.1145/273865.273933]
• 3: Benny Applebaum , Yuval Ishai , Eyal Kushilevitz, Cryptography in NC", Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.166-175, October 17-19, 2004 [doi>10.1109/FOCS.2004.20]
• 4: Eli Ben-Sasson , Madhu Sudan , Salil Vadhan , Avi Wigderson, Randomness-efficient low degree tests and short PCPs via epsilon-biased sets, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780631]
• 5: A. Cafure and G. Matera. Improved explicit estimates on the number of solutions of equations over a finite field. arXiv:math.NT/0405302 v1, 2004.
• 6: Mary Cryan , Peter Bro Miltersen, On Pseudorandom Generators in NC, Proceedings of the 26th International Symposium on Mathematical Foundations of Computer Science, p.272-284, August 27-31, 2001
• 7: Ming-Deh Huang , Yiu-Chung Wong, Solvability of systems of polynomial congruences modulo a large prime, Computational Complexity, v.8 n.3, p.227-257, Dec. 1999 [doi>10.1007/s000370050029]
• 8: Valentine Kabanets , Russell Impagliazzo, Derandomizing polynomial identity tests means proving circuit lower bounds, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780595]
• 9: Erich Kaltofen, Effective Noether irreducibility forms and applications, Journal of Computer and System Sciences, v.50 n.2, p.274-295, April 1995
• 10: S. Kalyanaraman and C. Umans. On obtaining pseudorandomness from error-correcting codes. Manuscript, 2005.
• 11: Adam R. Klivans , Daniel Spielman, Randomness efficient identity testing of multivariate polynomials, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.216-223, July 2001, Hersonissos, Greece [doi>10.1145/380752.380801]
• 12: S. Lang. Algebra. Addison-Wesley, Third edition, 1993.
• 13: M. Luby, B. Veličković, and A. Wigderson. Deterministic approximate counting of depth-2 circuits. In Proceedings of the 2nd Israeli Symposium on Theory of Computing and Systems, pages 18--24, 1993.
• 14: F. MacWilliams and N. Sloane. The Theory of Error-Correcting Codes. North-Holland, 1977.
• 15: Elchanan Mossel , Amir Shpilka , Luca Trevisan, On e-Biased Generators in NC0, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.136, October 11-14, 2003
• 16: J. Naor , M. Naor, Small-bias probability spaces: efficient constructions and applications, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.213-223, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100244]
• 17: Noam Nisan , Avi Wigderson, Hardness vs. randomness, Journal of Computer and System Sciences, v.49 n.2, p.149-167, Oct. 1994 [doi>10.1016/S0022-0000(05)80043-1]
• 18: W. A. Schmidt. Zur methode von Stepanov. Acta Arithmetica, 24:247--267, 1973.
• 19: W. M. Schmidt. A lower bound for the number of solutions of equations over finite fields. Journal of Number Theory, 6(6):448--480, 1974.
• 20: J. T. Schwartz, Fast Probabilistic Algorithms for Verification of Polynomial Identities, Journal of the ACM (JACM), v.27 n.4, p.701-717, Oct. 1980 [doi>10.1145/322217.322225]
• 21: Emanuele Viola, Pseudorandom Bits for Constant Depth Circuits with Few Arbitrary Symmetric Gates, Proceedings of the 20th Annual IEEE Conference on Computational Complexity, p.198-209, June 11-15, 2005 [doi>10.1109/CCC.2005.25]
• 22: A. Weil. Sur les courbes algébriques et les variétés qui s'en déduisent. Actualites Scientifiques et Industrielles, 1041, 1948.
• 23: Richard Zippel, Probabilistic algorithms for sparse polynomials, Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.216-226, June 01, 1979

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

General Terms:
Algorithms, Theory

Keywords:
derandomization, pseudorandomness