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 time t \ge n 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 assumption that there exists a function f \in \mathbf{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.
Mostly in the introduction.
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 randomized single-valued nondeterministic (SVN) circuits, we convert any randomized algorithm over inputs of length n running in time t \ge n 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). The latter derandomization result holds under weaker assumptions, of exponential lower bounds against deterministic SVN circuits.
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 assumption that there exists a function f \in \mathbf{E} that requires randomized SVN 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.
Rephrased the hardness assumption and added support for lower errors.
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 time t \ge n 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 assumption that there exists a function f \in \mathbf{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.
Minor revisions
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 time t \ge n 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 assumption that there exists a function f \in \mathbf{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.
