Unconditional pseudorandom generators for low degree polynomials

ABSTRACT

We give an explicit construction of pseudorandom generators against low degree polynomials over finite fields. We show that the sum of 2^d small-biased generators with error ε²O(d) is a pseudorandom generator against degree d polynomials with error ε. This gives a generator with seed length 2^O(d) log(n/ε). Our construction follows the recent breakthrough result of Bogadnov and Viola. Their work shows that the sum of d small-biased generators is a pseudo-random generator against degree d polynomials, assuming the Inverse Gowers Conjecture. However, this conjecture is only proven for d=2,3. The main advantage of our work is that it does not rely on any unproven conjectures.

REFERENCES

• 1: . Alon, O. Goldreich, J. Hastad, and R. Peralta. Simple constructions of almostk--wise independent random variables. In Random Structures & Algorithms, 3(3):289--304, 1992
• 2: . Bellare, D. Coppersmith, J. Hastad, M. Kiwi, and M. Sudan. Linearitytesting over characteristic two. In IEEE Transactions on Information Theory,42(6): 1781--1795, 1996.
• 3: Manuel Blum , Michael Luby , Ronitt Rubinfeld, Self-testing/correcting with applications to numerical problems, Journal of Computer and System Sciences, v.47 n.3, p.549-595, Dec. 1993 [doi>10.1016/0022-0000(93)90044-W]
• 4: Andrej Bogdanov, Pseudorandom generators for low degree polynomials, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060594]
• 5: 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]
• 6: Andrej Bogdanov , Emanuele Viola, Pseudorandom Bits for Polynomials, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.41-51, October 21-23, 2007 [doi>10.1109/FOCS.2007.56]
• 7: . Green and T. Tao. An inverse theorem for the Gowers U3 norm.To appear in Proceedings of the Edinburgh Mathematical Society.
• 8: . Green and T. Tao, The distribution of polynomials overfinite fields, with applications to the Gowers norms. preprint.
• 9: Shachar Lovett , Roy Meshulam , Alex Samorodnitsky, Inverse conjecture for the gowers norm is false, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374454]
• 10: . Luby, B. Velickovic, and A. Wigderson. DeterministicApproximate Counting of Depth--2 Circuits. In Proceedings ofthe 2nd Israeli Symposium on Theoretical Computer Science(ISTCS), pages 18--24, 1993.
• 11: 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]
• 12: Alex Samorodnitsky, Low-degree tests at large distances, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250864]
• 13: Alex Samorodnitsky , Luca Trevisan, Gowers uniformity, influence of variables, and PCPs, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132519]
• 14: . Viola. New correlation bounds for GF(2) polynomialsusing Gowers uniformity. In Electronic Colloquium onComputational Complexity, Technical Report TR06--097, 2006.http://www.eccc.uni--trier.de/eccc.
• 15: Emanuele Viola, Pseudorandom Bits for Constant-Depth Circuits with Few Arbitrary Symmetric Gates, SIAM Journal on Computing, v.36 n.5, p.1387-1403, December 2006 [doi>10.1137/050640941]
• 16: Emanuele Viola, The Sum of d Small-Bias Generators Fools Polynomials of Degree d, Proceedings of the 2008 IEEE 23rd Annual Conference on Computational Complexity, p.124-127, June 22-26, 2008 [doi>10.1109/CCC.2008.16]
• 17: Emanuele Viola , Avi Wigderson, Norms, XOR Lemmas, and Lower Bounds for GF(2) Polynomials and Multiparty Protocols, Proceedings of the Twenty-Second Annual IEEE Conference on Computational Complexity, p.141-154, June 13-March 16, 2007 [doi>10.1109/CCC.2007.15]

INDEX TERMS

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

General Terms:
Theory

Keywords:
fourier analysis, low degree tests, pseudorandom generators