Practical use of probability amplification for randomized algorithms - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T09:54:31Z http://mathoverflow.net/feeds/question/35090 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/35090/practical-use-of-probability-amplification-for-randomized-algorithms Practical use of probability amplification for randomized algorithms Marcos Villagra 2010-08-10T08:07:04Z 2010-08-10T22:52:02Z <p>Normally a 2-sided error randomized algorithm will have some constant error $\varepsilon &lt; 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.</p> <p>My question is:</p> <p>(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$.</p> <p>(2) What about an exponentially faster decreasing error? Here it seems that we don't need to repeat the algorithm at all.</p> <p>The same questions apply for 1-sided and 0-sided errors.</p> http://mathoverflow.net/questions/35090/practical-use-of-probability-amplification-for-randomized-algorithms/35091#35091 Answer by Suresh Venkat for Practical use of probability amplification for randomized algorithms Suresh Venkat 2010-08-10T08:48:45Z 2010-08-10T08:48:45Z <p>You cannot in general replace the inverse polynomial by an inverse exponential unless BPP = PP, which is highly unlikely. </p> http://mathoverflow.net/questions/35090/practical-use-of-probability-amplification-for-randomized-algorithms/35119#35119 Answer by Robin Kothari for Practical use of probability amplification for randomized algorithms Robin Kothari 2010-08-10T14:52:32Z 2010-08-10T14:52:32Z <p>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.</p> <p>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$.</p> <p>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. </p>