Pseudo-random generators for all hardnesses
Given a function with circuit complexity s, we construct a pseudo-random generator that stretches a random seed of length into a string of m=s?(1) pseudo-random bits that fool circuits of size m. The construction works for any hardness s, giving an optimal hardness vs. randomness tradeoff with a direct and self-contained proof. A key element in our construction is an augmentation of the standard low-degree extension encoding that exploits the field structure of the underlying space in a new way.
low-degree extension pseudo-random number generators derandomization complexity classes