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.