What is the fastest known simulation of BPP using Las Vegas algorithms? $\mathsf{BPP}$ and $\mathsf{ZPP}$ are two of basic probabilistic complexity classes.

$\mathsf{BPP}$ is the class of languages decided by probabilistic polynomial-time Turing algorithms where the probability of algorithm returning an incorrect answer is bounded, i.e. the error probability is at most $\frac{1}{3}$ (for both YES and NO instances).

On the other hand,
$\mathsf{ZPP}$ algorithms can be viewed as those probabilistic algorithms 
which never return an incorrect answer, whenever they return an answer it is correct.
However their running-time is not bounded by a polynomial, they run in expected polynomial.

Let $\mathsf{ZPTime}(f)$ be the class of language decided by probabilistic algorithms with zero error probability and expected running-time $f$. These are also referred to as Las Vegas algorithms and $\mathsf{ZPP} = \mathsf{ZPTime}(n^{O(1)})$.

My question is what is best know simulation of $\mathsf{BPP}$ algorithms using Las Vegas algorithms? Can we simulate them in subexponential expected time? Is there any known improvement over the trivial brute-force simulation which takes exponential time?

More formally, do we know if 
$\mathsf{BPP} \subseteq \mathsf{ZPTime}(2^{O(n^{\epsilon})})$ or $\mathsf{BPP} \subseteq \mathsf{ZPTime}(2^{n-n^{\epsilon}})$ for some $\epsilon&gt;0$?
First, observe that if $\mathsf{BPP} \subseteq \mathsf{ZPTIME}[2^{n^{c}}]$ for some constant $c$, then $\mathsf{BPP} \neq \mathsf{NEXP}$. (Proof by nondeterministic time hierarchy.) So proving such an inclusion would be significant, not just because it's an improved simulation but also would yield the first progress on randomized time lower bounds in decades.

Next, consider the class $\mathsf{PromiseBPP}$, for which the following problem is "$\mathsf{PromiseBPP}$-hard":


  Circuit Approximation Probability Problem (CAPP):  Given a circuit $C$, output the acceptance probability of $C$ to within a $1/6$ additive factor. 


Results of Impagliazzo, Kabanets, and Wigderson 2002 imply that a $2^{n^{\varepsilon}}$ time zero-error algorithm for CAPP (where $n$ is the size of $C$) would imply $\mathsf{NEXP} \not\subset \mathsf{P/poly}$. In STOC'10, I extended this to show: supposing for every $C$ with $k$ input bits and $n$ size, one can compute CAPP nondeterministically (so, zero-error suffices) in $2^{k-\omega(\log k)}\mathrm{poly}(n)$ time, then $\mathsf{NEXP} \not\subset \mathsf{P/poly}$. That is, there are certainly problems computable with two-sided-error randomness, for which zero-error algorithms that even mildly beat exhaustive search would imply circuit lower bounds. I believe this should be interpreted as a possible method for proving lower bounds; your mileage may vary.

Notice that even proving $\mathsf{RP} \subseteq \mathsf{ZPTIME}[2^{n^{\varepsilon}}]$ is also open, and proving that would also imply lower bounds: by Kabanets and Impagliazzo 2004, if polynomial identity testing (a $\mathsf{coRP}$ problem) is in $\mathsf{ZPTIME}[2^{n^{\varepsilon}}]$ for all $\varepsilon &gt; 0$, then we have lower bounds for either the Permanent or $\mathsf{NEXP}$. Recently (upcoming in STOC'13), I proved unconditionally that either $\mathsf{BPP} \subseteq \mathsf{ioZPTIME}[2^{n^{\varepsilon}}]/n^{\varepsilon}$ or $\mathsf{RTIME}[2^n]$ has $n^c$ size circuits, building on the "easy witness" method of Kabanets. This implies two things: 


There is a $c$ such that for all $\varepsilon &gt; 0$, $\mathsf{RP}$ is unconditionally in $\mathsf{ioZPTIME}[2^{n^{\varepsilon}}]/n^c$ -- this is about the best unconditional derandomization of $\mathsf{RP/BPP}$ in $\mathsf{ZPP}$ that we know so far. 
To start getting interesting subexponential simulations of $\mathsf{BPP}$, you "only" have to assume $\mathsf{RTIME}[2^n]$ doesn't have fixed-polynomial-size circuits.