Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > BLACK-BOX PROOFS:
Reports tagged with black-box proofs:
TR21-153 | 9th November 2021
Ronen Shaltiel, Emanuele Viola

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

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 of explicit hard functions. A high-end PRG'' with seed length $r=O(\log m)$ (implying BPP=P) was achieved in a seminal work of Impagliazzo and Wigderson (STOC 1997), assuming \textsc{the ... more >>>

ISSN 1433-8092 | Imprint