SCIENCE@home

Nearly Optimal Pseudorandomness From Hardness

Dean Doron,Dana Moshkovitz,Justin Oh,David Zuckerman

Published 2020 in IEEE Annual Symposium on Foundations of Computer Science

ABSTRACT

Existing proofs that deduce $\text{BPP} =\mathrm{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\geq 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 + α)log s, under the assumption that there exists a function f ∊ E that requires randomized SVN circuits of size at least 2(1−α')n, where. α=O(α'). The construction uses, among other ideas, a new connection between pseudoentropy generators and locally list recoverable codes.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-100 of 100 references · Page 1 of 1

CITED BY

Showing 1-36 of 36 citing papers · Page 1 of 1