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.