## On the feasibility of a seemingly
modest challenge in quantified derandomization

by Roei Tell
The starting point of my work with Avi on quantified derandomization
(i.e., On Derandomizing Algorithms that Err Extremely Rarely)
was the following challenge:
*Given a polynomial-size circuit that evalauate to 1
on all but polynomially-many inputs, can you find an input
that evaluates to 1 in time that is significantly smaller
than obvious?*
Specifically, if the Boolean circuit takes an n-bit input,
has size $S(n)=poly(n)$
and evaluates to 0 on at most $B(n)=poly(n)$ (bad) inputs,
can a string that evalutes to 1 be found in time $o(B(n) \cdot S(n))$?

Roei Tell just informed me that this challenge may be much
more difficulty than we thought, since a version of it would imply
that NP is not contained in $SIZE(n^k)$, for any constant k.
Specifically, he proved this w.r.t finding-time $B(n)^{1-\eps}$,
for any constant $\eps > 0$, rather than w.r.t time $o(B(n)S(n))$.

The proof uses the celebrated result of Murray and Williams
that refers to the standard derandomization problem
(i.e., at most half of the $m$-bit inputs are bad)
for $m$-bit circuits of size $2^{\delta m}$ and time $2^{(1-\delta)m}$,
and consists of employing error-reduction with non-standard parameters.
Specifically, we invoke the $m$-bit circuit $\exp(O(m))$ many times,
while employing error reduction that yields error that is exponential
(to base 2) in the number of random bits.
That is, letting $n$ be exponential in $m$,
the error on the resulting $n$-bit circuit is $B(n)\cdot 2^{-n}$,
where $B(n)=\poly(n)=\exp(O(m))$.
Note that such an error-reduction can be obatined by using
the extractor of Guruswami, Umans, and Vadhan:
The min-entropy bound is merely $\log_2 B(n)=c'm$,
for any constant $c'>1$, whereas the number of invocations
of the original circuit is $\poly(n)$.

For more details see Roei's private communication to me,
where the foregoing result appears as Thm 3.
Both Thms 2 and 3 will appear in a survey on quantified derandomization
that Roei is currently writing.

**Update (Aug 18)**: The survey has appeared as
ECCC TR21-120;
Thms 2 and 3 appear there as Thm 6.1 and 6.2, resp.

Back to
list of Oded's choices.