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