Pseudo-random generators for all hardnesses

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

Authors

• Chris Umans

Keywords

No keywords are indexed for this paper.