We're sorry but this page doesn't work properly without JavaScript enabled. Please enable it to continue.
Feedback

Nearly Optimal Pseudorandomness From Hardness

Formal Metadata

Title
Nearly Optimal Pseudorandomness From Hardness
Title of Series
Number of Parts
12
Author
License
CC Attribution - NonCommercial - NoDerivatives 4.0 International:
You are free to use, copy, distribute and transmit the work or content in unchanged form for any legal and non-commercial purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Identifiers
Publisher
Release Date
Language

Content Metadata

Subject Area
Genre
Abstract
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.