Open Collections

Description

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 nondeterministic circuits, we convert any randomized algorithm that errs rarely into a deterministic algorithm with a similar running time (with pre-processing), and any general randomized algorithm into a deterministic algorithm whose runtime is slower by a nearly linear multiplicative factor. Our results follow from a new, nearly optimal, explicit pseudorandom generator fooling circuits of size s with seed length (1+alpha)log s for an arbitrarily small constant alpha>0, under the assumption that there exists a function f in E that requires nondeterministic circuits of size at least 2^{(1-alpha')n}, where alpha = O(alpha'). The construction uses, among other ideas, a new connection between pseudoentropy generators and locally list recoverable codes.