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

$\endgroup$
5
  • $\begingroup$ You mean P(A(x) accepts) > 1/2 + epsilon in the first case? $\endgroup$ Jan 26 '12 at 19:47
  • $\begingroup$ You need $\epsilon_1 + \epsilon_2 \leq 1/2 - 1/\mathrm{poly}(n)$. $\endgroup$ 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$ 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$.

$\endgroup$
3
  • 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$ 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.