$\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>0$?
What is the fastest known simulation of BPP using Las Vegas algorithms?
cc.complexity theory;complexity classes;randomness;randomized algorithms