3
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ The practicality of how many times you'll need to repeat a randomized algorithm will depend on the application. $\endgroup$
    – Ryan Williams
    Commented Aug 10, 2010 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
    Commented Aug 10, 2010 at 22:49

2 Answers 2

Reset to default
5
$\begingroup$

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.

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

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

Improve this answer
$\endgroup$
4
  • $\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
    Commented Aug 10, 2010 at 9:01
  • $\begingroup$ actually, it doesn't say that we can replace an inverse polynomial by an inverse exponential. $\endgroup$
    – Marcos Villagra
    Commented Aug 10, 2010 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
    Commented Aug 10, 2010 at 16:44
  • $\begingroup$ argghh. sorry. Thanks for the correction. $\endgroup$
    – Suresh Venkat
    Commented Aug 10, 2010 at 17:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .