Open Collections

Nearly Optimal Pseudorandomness From Hardness

Banff International Research Station for Mathematical Innovation and Discovery

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.

Mathematics; Computer science; Theoretical computer science

video/mp4

Author affiliation: University of Texas - Austin

2020-01-05

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/73099

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/