4
$\begingroup$

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

Improve this question
$\endgroup$
  • $\begingroup$ You mean P(A(x) accepts) > 1/2 + epsilon in the first case? $\endgroup$ – Marcin Kotowski Jan 26 '12 at 19:47
  • $\begingroup$ You need $\epsilon_1 + \epsilon_2 \leq 1/2 - 1/\mathrm{poly}(n)$. $\endgroup$ – Mahdi Cheraghchi Jan 26 '12 at 19:56
  • $\begingroup$ @MarcinKotowski No. I want to see what happens when its 1/2 or smaller. $\endgroup$ – Randomizer Jan 26 '12 at 20:55
  • $\begingroup$ @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. $\endgroup$ – Randomizer Jan 26 '12 at 21:00
  • $\begingroup$ I posted a more detailed answer below. $\endgroup$ – Mahdi Cheraghchi Jan 26 '12 at 23:12
6
$\begingroup$

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

Improve this answer
$\endgroup$
  • 2
    $\begingroup$ The standard and, IMHO, easier to analyze algorithm is to accept iff the fraction exceeds $(\epsilon'_1+\epsilon_2)/2$, with no random guesses. $\endgroup$ – Emil Jeřábek Jan 27 '12 at 12:00
  • $\begingroup$ @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$. $\endgroup$ – Randomizer Jan 28 '12 at 0:44
  • 1
    $\begingroup$ @MCH Thanks. I was trying to use majority to decide while here the natural generalization to majority idea was to use the fraction to decide. $\endgroup$ – Randomizer Jan 28 '12 at 0:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.