Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > JUSTIN OH:
All reports by Author Justin Oh:

TR19-099 | 29th July 2019
Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman

Nearly Optimal Pseudorandomness From Hardness

Existing proofs that deduce $\mathbf{BPP}=\mathbf{P}$ from circuit lower bounds convert randomized algorithms into deterministic algorithms with a large polynomial slowdown. We convert randomized algorithms into deterministic ones with little slowdown. Specifically, assuming exponential lower bounds against nondeterministic circuits, we convert any randomized algorithm over inputs of length $n$ running in ... more >>>




ISSN 1433-8092 | Imprint