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

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

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