On Hardness Assumptions Needed for "Extreme High-End'' PRGs and Fast Derandomization

Ronen Shaltiel, Emanuele Viola

The hardness vs.~randomness paradigm aims to explicitly construct pseudorandom generators $G:\{0,1{\}}^r\to \{0,1{\}}^m$ that fool circuits of size $m$, assuming the existence…