ECCC-Report TR13-152https://eccc.weizmann.ac.il/report/2013/152Comments and Revisions published for TR13-152en-usThu, 22 Sep 2016 10:10:48 +0300
Revision 2
| On Derandomizing Algorithms that Err Extremely Rarely |
Oded Goldreich,
Avi Wigderson
https://eccc.weizmann.ac.il/report/2013/152#revision2{\em Does derandomization of probabilistic algorithms become easier when the number of ``bad'' random inputs is extremely small?}
In relation to the above question, we put forward the following {\em quantified derandomization challenge}:
For a class of circuits $\cal C$ (e.g., P/poly or $AC^0,AC^0[2]$) and a bounding function $B:\N\to\N$ (e.g., $B(n)=n^{\log n}$ or $B(n)=\exp(n^{0.99}))$),
given an $n$-input circuit $C$ from $\cal C$
that evaluates to~1 on all but at most $B(n)$ of its inputs, find (in deterministic polynomial-time) an input $x$ such that $C(x)=1$.
Indeed, the {\em standard}\/ derandomization challenge for the class $\cal C$ corresponds to the case of $B(n)=2^n /2$ (or to $B(n)=2^n /3$ for the two-sided version case).
Our main results regarding the new {\em quantified}\/ challenge are:
\begin{enumerate}
\item
Solving the {\em quantified}\/ derandomization challenge for the class $AC^0$ and every sub-exponential bounding function (e.g., $B(n)=\exp(n^{0.999})$).
\item
Showing that solving the {\em quantified}\/ derandomization challenge for the class $AC^0[2]$ and any sub-exponential bounding function (e.g., $B(n)=\exp(n^{0.001})$), implies solving the {\em standard}\/ derandomization challenge for the class $AC^0[2]$ (i.e., for $B(n)=2^n/2$).
\end{enumerate}
Analogous results are obtained also for stronger (Black-box) forms of efficient derandomization like hitting-set generators.
We also obtain results for other classes of computational devices including log-space algorithms and Arithmetic circuits. For the latter we present a deterministic polynomial-time hitting set generator for the class of $n$-variate polynomials of degree $d$ over $GF(2)$ that evaluate to~0 on at most
an $O(2^{-d})$ fraction of their inputs.
In general, the quantified derandomization problem raises a variety of seemingly unexplored questions about many randomized
complexity classes, and may offer a tractable approach to unconditional derandomization for some of them.Thu, 22 Sep 2016 10:10:48 +0300https://eccc.weizmann.ac.il/report/2013/152#revision2
Revision 1
| On Derandomizing Algorithms that Err Extremely Rarely |
Oded Goldreich,
Avi Wigderson
https://eccc.weizmann.ac.il/report/2013/152#revision1{\em Does derandomization of probabilistic algorithms become easier when the number of ``bad'' random inputs is extremely small?}
In relation to the above question, we put forward the following {\em quantified derandomization challenge}:
For a class of circuits $\cal C$ (e.g., P/poly or $AC^0,AC^0[2]$) and a bounding function $B:\N\to\N$ (e.g., $B(n)=n^{\log n}$ or $B(n)=\exp(n^{0.99}))$),
given an $n$-input circuit $C$ from $\cal C$
that evaluates to~1 on all but at most $B(n)$ of its inputs, find (in deterministic polynomial-time) an input $x$ such that $C(x)=1$.
Indeed, the {\em standard}\/ derandomization challenge for the class $\cal C$ corresponds to the case of $B(n)=2^n /2$ (or to $B(n)=2^n /3$ for the two-sided version case).
Our main results regarding the new {\em quantified}\/ challenge are:
\begin{enumerate}
\item
Solving the {\em quantified}\/ derandomization challenge for the class $AC^0$ and every sub-exponential bounding function (e.g., $B(n)=\exp(n^{0.999})$).
\item
Showing that solving the {\em quantified}\/ derandomization challenge for the class $AC^0[2]$ and any sub-exponential bounding function (e.g., $B(n)=\exp(n^{0.001})$), implies solving the {\em standard}\/ derandomization challenge for the class $AC^0[2]$ (i.e., for $B(n)=2^n/2$).
\end{enumerate}
Analogous results are obtained also for stronger (Black-box) forms of efficient derandomization like hitting-set generators.
We also obtain results for other classes of computational devices including log-space algorithms and Arithmetic circuits. For the latter we present a deterministic polynomial-time hitting set generator for the class of $n$-variate polynomials of degree $d$ over $GF(2)$ that evaluate to~0 on at most
an $O(2^{-d})$ fraction of their inputs.
In general, the quantified derandomization problem raises a variety of seemingly unexplored questions about many randomized
complexity classes, and may offer a tractable approach to unconditional derandomization for some of them.Mon, 16 Jun 2014 16:29:18 +0300https://eccc.weizmann.ac.il/report/2013/152#revision1
Paper TR13-152
| On Derandomizing Algorithms that Err Extremely Rarely |
Oded Goldreich,
Avi Wigderson
https://eccc.weizmann.ac.il/report/2013/152{\em Does derandomization of probabilistic algorithms become easier when the number of ``bad'' random inputs is extremely small?}
In relation to the above question, we put forward the following {\em quantified derandomization challenge}:
For a class of circuits $\cal C$ (e.g., P/poly or $AC^0,AC^0[2]$) and a bounding function $B:\N\to\N$ (e.g., $B(n)=n^{\log n}$ or $B(n)=\exp(n^{0.99}))$),
given an $n$-input circuit $C$ from $\cal C$
that evaluates to~1 on all but at most $B(n)$ of its inputs, find (in deterministic polynomial-time) an input $x$ such that $C(x)=1$.
Indeed, the {\em standard}\/ derandomization challenge for the class $\cal C$ corresponds to the case of $B(n)=2^n /2$ (or to $B(n)=2^n /3$ for the two-sided version case).
Our main results regarding the new {\em quantified}\/ challenge are:
\begin{enumerate}
\item
Solving the {\em quantified}\/ derandomization challenge for the class $AC^0$ and every sub-exponential bounding function (e.g., $B(n)=\exp(n^{0.999})$).
\item
Showing that solving the {\em quantified}\/ derandomization challenge for the class $AC^0[2]$ and any sub-exponential bounding function (e.g., $B(n)=\exp(n^{0.001})$), implies solving the {\em standard}\/ derandomization challenge for the class $AC^0[2]$ (i.e., for $B(n)=2^n/2$).
\end{enumerate}
Analogous results are obtained also for stronger (Black-box) forms of efficient derandomization like hitting-set generators.
We also obtain results for other classes of computational devices including log-space algorithms and Arithmetic circuits. For the latter we present a deterministic polynomial-time hitting set generator for the class of $n$-variate polynomials of degree $d$ over $GF(2)$ that evaluate to~0 on at most
an $O(2^{-d})$ fraction of their inputs.
In general, the quantified derandomization problem raises a variety of seemingly unexplored questions about many randomized
complexity classes, and may offer a tractable approach to unconditional derandomization for some of them.Thu, 07 Nov 2013 09:19:23 +0200https://eccc.weizmann.ac.il/report/2013/152