Suppose that a randomized algorithm uses $r$ random bits. The lowest error probability one can expect (falling short of a deterministic algorithm with 0 error) is $2^{-\Omega(r)}$. Which randomized algorithms achieve such minimal error probability?A couple of examples that come to mind are: Sampling algorithms, e.g., where one wants to estimate the size of aset for which one can check membership. If one samples uniformly atrandom the elements to check, the Chernoff bound guarantees anexponentially small error probability. The Karger-Klein-Tarjan algorithm for computing minimum spanning tree. The algorithm picks each edge with probability 1/2, and recursively finds the MST in the sample. One can use Chernoff to argue that it's exponentially unlikely there'll be 2n+0.1m of the edges that are better than the tree (i.e., one would prefer to take them over one of the tree edges).Can you think of other examples?Following Andras' answer below: Indeed, every polynomial time algorithm can be converted to a slower polynomial time algorithm with exponentially small error probability. My focus is on algorithms that are as efficient as possible. In particular, for the two examples I gave there are deterministic polynomial time algorithms that solve the problems. The interest in the randomized algorithms is due to their efficiency. 
Which randomized algorithms have exponentially small error probability?
randomized algorithms