# BPP Error Reduction

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)?

• You mean P(A(x) accepts) > 1/2 + epsilon in the first case? – Marcin Kotowski Jan 26 '12 at 19:47
• You need $\epsilon_1 + \epsilon_2 \leq 1/2 - 1/\mathrm{poly}(n)$. – Mahdi Cheraghchi Jan 26 '12 at 19:56
• @MarcinKotowski No. I want to see what happens when its 1/2 or smaller. – Randomizer Jan 26 '12 at 20:55
• @MCH I was suspecting that $\epsilon_2 < 1/2-\epsilon_1$ (almost the same as what you said), but I couldn't prove it. I got confused in the middle of my proof idea. – Randomizer Jan 26 '12 at 21:00
• I posted a more detailed answer below. – Mahdi Cheraghchi Jan 26 '12 at 23:12

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$.
• The standard and, IMHO, easier to analyze algorithm is to accept iff the fraction exceeds $(\epsilon'_1+\epsilon_2)/2$, with no random guesses. – Emil Jeřábek Jan 27 '12 at 12:00
• @EmilJeřábek I know what you mean, but the above algorithm highlights that it doesn't matter how your algorithm answers when the fraction is between $\epsilon_2$ and $\epsilon'_1$. – Randomizer Jan 28 '12 at 0:44