Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
Consider the class of all languages $L$ that have a randomized algorithm $A$ that runs in worst-case polynomial time such that for any input $x$ if $x \in L$ then $Pr[A(x)\quad \textrm{accepts}] \ge 1/2 - \epsilon_1$; otherwise $Pr[A(x) \quad \textrm{accepts}] \le \epsilon_2$.
Is there any $\epsilon_1 \ge 0$ and $\epsilon_2 > 0$ that make this class equal to BPP? If it is, what are the largest values $\epsilon_1$ and $\epsilon_2$ that we can get (perhaps, relative to each other)?
Set $\epsilon'_1 := 1/2 - \epsilon_1$. Run $A$ independently $T$ times. If the fraction of accepts exceeds $\epsilon'_1$ (falls below $\epsilon_2$), then accept (reject). Otherwise output a random guess. Use Chernoff bounds to show that the probability of ending up with a wrong value is exponentially small in $T$, more precisely the error probability can be upper bounded by $\exp(-T |\epsilon'_1 - \epsilon_2| )$. Therefore as long as $|\epsilon'_1 - \epsilon_2| \geq 1/\mathrm{poly}(n)$ (in other words, $\epsilon_1 + \epsilon_2 \leq 1/2 - 1/\mathrm{poly}(n)$), you can choose a polynomially bounded $T$ to bring the error probability below $1/3$.
