Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



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

Revisions: 1

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