Pseudo-random generators for all hardnesses

摘要

Given a function f:{0,1}logn→{0,1} with circuit complexity s, we construct a pseudo-random generator that stretches a random seed of length O(logn) 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.