What is the fastest known simulation of BPP using Las Vegas algorithms?

Question

$\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$?

Answer 1

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 > 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:

1. There is a $c$ such that for all $\varepsilon > 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.

2. 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.

Answer 2

It depends on what assumptions you are willing to make.

Under certain hardness assumptions, namely $E \not\subseteq SIZE(2^{\varepsilon n})$, you get that $P = BPP$. This in particular implies that $BPP = ZPP$, and therefore that every language $L \in BPP$ is accepted by a Las Vegas machine (see "P=BPP unless E has Subexponential Circuits: Derandomizing the XOR Lemma", by Impagliazzo and Wigderson).

You can also make a milder hardness assumption, namely, that $ZPE \not\subseteq \rm{io-DTIME}(2^{\varepsilon n})$, and get that $BPP = ZPP$ (see Lemma 46 in "In search of an easy witness: Exponential time vs. probabilistic polynomial time" by Impagliazzo, Kabanets and Wigderson).

Answer 3

Barring any advances in derandomization, it seems to me as though the requirement that the Las Vegas Machine makes no mistakes is crucial, so that there is little to no benefit to having randomness at all in this case.

For a BPP language $L$ decided by a suitable algorithm $A$, which acts on inputs $x \in \{0,1\}^n$ and a random string $r \in \{0,1\}^{N(n)}$ representing its random choices, the zero-error criterion implies that the Las Vegas machine must ascertain for certain which of the two cases $$\Pr_r(\text{$A$ accepts $(x,r)$}) \geqslant \tfrac{2}{3} \quad\text{or}\quad \Pr_r(\text{$A$ accepts $(x,r)$}) \leqslant \tfrac{1}{3}$$ holds. If we are given no further information about $A$, then this is essentially an oracle promise problem: given an oracle $A'$ computing $A'(r) = A(x,r)$, and given the promise that $A'$ yields one output $a \in \{0,1\}$ for at least twice as many inputs as the opposite output $1-a$, determine which output is more common.

Although the Las Vegas Machine may use random techniques, if we are indeed forced to treat $A'$ as an oracle, we can see that the only strategy available to a Las Vegas machine is to take a relatively thorough (though not exhaustive) survey of the random strings $r$, to see what answer is given for each. It can only be sure if it finds more than $2^{N(n)}\!/3$ distinct strings $r$ which all give rise to the same output; otherwise, with small (but non-zero!) probability, it may be unlucky and obtain a non-representative sample of the possible outputs. To obtain zero error, it must sample at least $2^{N(n)}\!/3$ inputs $r$.

Because the Las Vegas machine must inspect at least a constant fraction of all of the possible random strings $r$, asymptotically we're no better off than if we deterministically tested all possible random strings. We get no asymptotic advantage in simulating BPP algorithms randomly in a zero-error setting, beyond what we can do deterministically by brute-force.

Note that this same argument gives rise to an oracle separation between BPP and ZPP, i.e. there is an oracle $A$ such that $$\mathsf{ZPP}^A \subsetneqq \mathsf{BPP}^A$$ because the ZPP algorithm takes exponential time, while a BPP algorithm can solve the question about the oracle in a single query and succeed with bounded error. However, it doesn't tell you any more than what you suspected already (that the simulation overhead may be worse than polynomial) nor that the asymptotics are just as bad as a naive deterministic simulation.