Pseudorandom Bits for Polynomials

By Frank McSherry, Kunal Talwar. 2007

1,931 citations recorded by the source corpus.

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 : FsrarrFn 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 F2 = {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 F2.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Algorithms & Complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

  1. Jonathan Ullman
  2. Abhradeep Thakurta
  3. Vitaly Feldman
  4. Peter Kairouz
  5. Philip S. Yu
  6. Yu-Xiang Wang
  7. Daniel Kifer
  8. Adam D. Smith

In Computational Theory and Mathematics

  1. Jonathan Ullman
  2. Salil P. Vadhan
  3. Cynthia Dwork
  4. Adam D. Smith
  5. Aaron Roth
  6. Mark Bun
  7. Thomas Steinke
  8. Vitaly Feldman

In Discrete Mathematics and Combinatorics

  1. Jonathan Ullman
  2. Adam D. Smith
  3. Cynthia Dwork
  4. Aaron Roth
  5. Thomas Steinke
  6. Kobbi Nissim
  7. Kamalika Chaudhuri
  8. Salil P. Vadhan

In Algorithms & Complexity

  1. Jonathan Ullman
  2. Vitaly Feldman
  3. Ninghui Li
  4. Jayadev Acharya
  5. Ziteng Sun
  6. Uri Stemmer
  7. Kunal Talwar
  8. Thomas Steinke

Citations in the corpus