Revision #2 Authors: Oded Goldreich, Avi Wigderson

Accepted on: 22nd September 2016 10:10

Downloads: 317

Keywords:

{\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.

Correcting inaccuracies and clarifying the statement and proof of Thm 3.4 (which was added in previous revision).

Revision #1 Authors: Oded Goldreich, Avi Wigderson

Accepted on: 16th June 2014 16:29

Downloads: 664

Keywords:

{\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.

Added Sec 3.3 and Apdx A.1.

In Sec 3.3 we show that for $B(n)=\exp(n/{\rm poly}(\log n))$, the $(AC0,B)$-search is not easier than standard approximate counting for AC0.

In Apdx A.1 we present a (deterministic) log-space procedure, due to Mike Saks (from the 1990s), that handles $2^{0.999n}$ bad inputs.

TR13-152 Authors: Oded Goldreich, Avi Wigderson

Publication: 7th November 2013 09:19

Downloads: 1671

Keywords:

{\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.