ECCC-Report TR19-099https://eccc.weizmann.ac.il/report/2019/099Comments and Revisions published for TR19-099en-usMon, 07 Sep 2020 04:23:48 +0300
Revision 3
| Nearly Optimal Pseudorandomness From Hardness |
Dean Doron,
David Zuckerman,
Dana Moshkovitz,
Justin Oh
https://eccc.weizmann.ac.il/report/2019/099#revision3Existing 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. Mon, 07 Sep 2020 04:23:48 +0300https://eccc.weizmann.ac.il/report/2019/099#revision3
Revision 2
| Nearly Optimal Pseudorandomness From Hardness |
Dean Doron,
David Zuckerman,
Dana Moshkovitz,
Justin Oh
https://eccc.weizmann.ac.il/report/2019/099#revision2Existing 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. Thu, 16 Apr 2020 05:25:28 +0300https://eccc.weizmann.ac.il/report/2019/099#revision2
Revision 1
| Nearly Optimal Pseudorandomness From Hardness |
Dean Doron,
David Zuckerman,
Dana Moshkovitz,
Justin Oh
https://eccc.weizmann.ac.il/report/2019/099#revision1Existing 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. Sat, 02 Nov 2019 05:09:16 +0200https://eccc.weizmann.ac.il/report/2019/099#revision1
Paper TR19-099
| Nearly Optimal Pseudorandomness From Hardness |
Dean Doron,
David Zuckerman,
Dana Moshkovitz,
Justin Oh
https://eccc.weizmann.ac.il/report/2019/099Existing 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. Mon, 29 Jul 2019 22:55:04 +0300https://eccc.weizmann.ac.il/report/2019/099