Normally a 2-sided error randomized algorithm will have some constant error $\varepsilon < 1/2$. We know that we can replace the error term for any inverse polynomial. And the inverse polynomial can be replaced for an inverse exponential. Say that we have an algorithm $A$ with $\varepsilon_A=1/p(n)$ for some polynomial $p$ that runs in $T(n)$ steps, and by repeating the algorithm $O(\log \frac{1}{\varepsilon})$ times we obtain and algorithm $B$ with success probability close to 1 but with a logarithmic overhead.

My question is:

(1) If the error decreases polynomially faster, for practical purposes, do we still need to repeat the algorithm several times? Because if we do so we get a logarithmic term (which is not desired), but leaving it as it is, the algorithm will still have a success probability close to 1 for sufficiently large $n$.

(2) What about an exponentially faster decreasing error? Here it seems that we don't need to repeat the algorithm at all.

The same questions apply for 1-sided and 0-sided errors.

  • $\begingroup$ The practicality of how many times you'll need to repeat a randomized algorithm will depend on the application. $\endgroup$ – Ryan Williams Aug 10 '10 at 16:49
  • $\begingroup$ In several papers they sometimes use amplification and sometimes don't. So I was intrigue on that. It wasn't clear for me when to use it. $\endgroup$ – Marcos Villagra Aug 10 '10 at 22:49

There seems to be some confusion in your notation. When you says error $\epsilon$, do you mean the probability of failure is $\epsilon$, which means that the algorithm outputs the wrong answer with probability $\epsilon$. In this case, if $\epsilon$ is polynomially small, that's great. If you run it a few times you should keep getting good answers.

But then you talk about the case where the error is $1/2 - \epsilon$ (in the comments), where $\epsilon$ is inverse polynomial. This situation is bad, because your algorithm will seem to output random bits. Thus you should error amplify to get constant error (say 1% error). The number of steps taken for this is logarithmic in $1/\epsilon$.

So in conclusion, if the error is like $1/2 - 1/poly$, you can amplify this to 1/3 in polynomial time. Once your error is a constant, you can also amplify it to inverse exponential, i.e., $\epsilon = 1/exp$ in polynomial time.

  • $\begingroup$ yes, I'm misusing the notation, but you completely understood my question. Thanks for the reply, know is crystal clear. $\endgroup$ – Marcos Villagra Aug 10 '10 at 22:51

You cannot in general replace the inverse polynomial by an inverse exponential unless BPP = PP, which is highly unlikely.

  • $\begingroup$ In Arora and Barak, theorem 7.10 page 132 it says Let $L\subseteq\{0,1\}^*$ be a language and suppose there exists a polynomial-time PTM M s.t. for every $x\in \{0,1\}^*$, $Pr[M(x)=L(x)]\geq 1/2+n^{-c}$. Then for every constant $d>0$ there exists a polynomial-time PTM M' such that for every $x\in\{0,1\}^*$, $Pr[M'(x)=L(x)]\geq 1-2^{-n^d}$. Is my interpretation correct? Of course it's not saying anything about the running time. $\endgroup$ – Marcos Villagra Aug 10 '10 at 9:01
  • $\begingroup$ actually, it doesn't say that we can replace an inverse polynomial by an inverse exponential. $\endgroup$ – Marcos Villagra Aug 10 '10 at 10:36
  • 1
    $\begingroup$ Suresh: you can replace the error with inverse-exponential in poly(n). In fact the proofs of several results in complexity rely on this, such as Adleman's theorem. It doesn't imply PP=BPP because, in the process of making the error probability very low, you have also introduced poly(n) new random bits. So even if the probability of error becomes 1/2^{n^k}, there will be 2^{poly(n^k)} possible random bit strings. So you still cannot count exactly, or even close to that. $\endgroup$ – Ryan Williams Aug 10 '10 at 16:44
  • $\begingroup$ argghh. sorry. Thanks for the correction. $\endgroup$ – Suresh Venkat Aug 10 '10 at 17:25

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.