Abstract
We construct the first pseudo-random generators with logarithmic seed length that convert s bits of hardness into s^{\Omega(1)} bits of 2-sided pseudo-randomness, for any s. This improves [ISW00] and gives a direct proof of the optimal hardness vs. randomness tradeoff in [SU01]. 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.