"Nearly Optimal Pseudorandomness From Hardness" 
David Zuckerman (UT Austin)
Monday, January 13, 2020, 2:00pm
EBU3B, Room 4258
Existing proofs that deduce BPP=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 certain nondeterministic circuits, we convert any randomized algorithm running in time t to a deterministic one running in time t^{2+alpha} for an arbitrarily small constant alpha > 0. Such a slowdown is nearly optimal, as, under complexity-theoretic assumptions, there are problems with an inherent quadratic derandomization slowdown. We also convert any randomized algorithm that errs rarely into a deterministic algorithm having a similar running time (with pre-processing).
Our results follow from a new, nearly optimal, explicit pseudorandom generator fooling circuits of size s with seed length (1+\alpha)log s, under the above assumption. The construction uses, among other ideas, a new connection between pseudoentropy generators and locally list recoverable codes.
This is joint work with Dean Doron, Dana Moshkovitz, and Justin Oh.