computational complexity - Practical use of probability amplification for randomized algorithms

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.

• Next lie groups - A terminology issue with the Killing Form
• Previous sp.spectral theory - An inverse eigenvalue problem on Jacobi matrices