Which randomized algorithms have exponentially small error probability?

Question

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 a set for which one can check membership. If one samples uniformly at random the elements to check, the Chernoff bound guarantees an exponentially 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.

Answer 1

Impagliazzo and Zuckerman proved (FOCS'89, see here) that if a BPP algorithm uses $r$ random bits to achieve a correctness probability of at least 2/3, then, applying random walks on expander graphs, this can be improved to a correctness probability of $1-2^{-k}$, using $O(r+k)$ random bits. (Note: while the authors use the specific constant 2/3 in the abstract, it can be replaced with any other constant greater than 1/2.)

If we take $k=r$, this means that any BPP algorithm that achieves a constant error probability $< 1/2$, using $r$ random bits, can be (non-trivially) improved to have error probability $2^{-\Omega(r)}$. Thus, (unless I misunderstood something), the error probability of $\leq 2^{-\Omega(r)}$ is achievable for every problem in BPP.

Answer 2

I'm not sure this is what you're looking for, but it's related:

Suppose I want to find a random $k$-bit prime number. The usual algorithm is to pick a random (odd) $k$-bit integer and run the Miller-Rabin primality test for $t$ rounds on it and repeat until a probable prime is found. What is the probability that this procedure returns a composite number? Call this probability $p_{k,t}$.

The standard analysis of the Miller-Rabin primality test shows that $t$ rounds gives a failure probability of at most $4^{-t}$. This, along with the prime number theorem, implies $$p_{k,t} \leq O(k\cdot 4^{-t}).$$

However, we are running the Miller-Rabin test on random inputs, so we can use an average-case error guarantee. We get a much better bound. In particular, for $t=1$, $$p_{k,1} \leq 2^{-(1-o(1))\frac{k \ln\ln k}{\ln k}} \leq 2^{-\tilde\Omega(k)}.$$ That is to say, we get an exponentially-small failure probability with only one repetition of the test!

See Erdös and Pomerance (1986), Kim and Pomerance (1989), and Dåmgard, Landrock, and Pomerance (1993) for more details.

This is not a decision problem and the amount of randomness used is $O(k^2)$ bits (although I suspect this can be easily reduced to $O(k)$). However, it's an interesting example where we get exponentially-small failure probability naturally.