Pseudorandom Bits for Polynomials

We present a new approach to constructing pseudorandom generators that fool low-degree polynomials over finite fields, based on the Gowers norm. Using this approach, we obtain the following main constructions of explicitly computable generators G: F s rarrF n that fool polynomials over a prime field F: (1) a generator that fools degree-2 (i. e. , quadratic) polynomials to within error 1/n, with seed length s = O(log n); (2) a generator that fools degree-3 (i. e. , cubic) polynomials to within error epsiv, with seed length s = O(Iog |F| n) + f(epsiv, F) where f depends only on epsiv and F (not on n), (3) assuming the "Gowers inverse conjecture, " for every d a generator that fools degree-d polynomials to within error epsiv, with seed length, s = O(dldrIog |F| n) + f(d, epsiv, F) where f depends only on d, epsiv, and F (not on n). We stress that the results in (1) and (2) are unconditional, i. e. do not rely on any unproven assumption. Moreover, the results in (3) rely on a special case of the conjecture which may be easier to prove. Our generator for degree-d polynomials is the component-wise sum of d generators for degree-l polynomials (on independent seeds). Prior to our work, generators with logarithmic seed length were only known for degree-1 (i. e. , linear) polynomials (Naor and Naor; SIAM J. Comput. , 1993). In fact, over small fields such as F 2 = {0, 1}, our results constitute the first progress on these problems since the long-standing generator by Luby, Velickovic and Wigderson (ISTCS1993), whose seed length is much bigger: s = exp (Omega(radiclogn)), even for the case of degree-2 polynomials over F 2.

Authors

• Andrej Bogdanov
• Emanuele Viola

Keywords

• Polynomials
• Testing
• Computer science
• Galois fields
• Stress
• Application software
• Complexity theory
• Algorithm design and analysis
• Cryptography
• Books
• Conjecture
• Quadratic Function
• Finite Field
• Linear Polynomial
• Seed Length
• Normal Function
• Linear Function
• End Of Section
• Polynomial Of Degree
• Constant Function
• Case Approach
• Directional Derivative
• Proof Of The Lemma
• Fourier Coefficients
• Test Classes
• Arbitrary Field
• Definition Of Norm
• Statistical Distance
• High-degree Polynomial