The proof is in the image below, taken from "Quantum Computing Since Democritus":

BPP subset P/Poly

Here's what I don't totally get: my understanding of random algorithms is that randomization is not done over the input space; the inputs are still worst case. So that when a random algorithm has some error, what I interpret that to mean is that given any input string to the algorithm, there is at most such-and-such probability of outputting a wrong answer.

If I take the same string $s$ and run it through the random algorithm with error rate $e<1$ an $n$ amount of times, I should expect $ne$ wrong answers.

I haven't been able to reconcile the above with the technique used in the linked proof; in particular, the jump from $2^{-n^2}$ being the error rate of the BPP algorithm to saying that a $2^{-n^2}$ fraction of random strings cause us to err. If someone could explain this proof a little more verbosely I think I'd find that very helpful.


1 Answer 1


What he here means by a "random string" is not an element of the input space, but rather a string of random choices, i.e. a series of coin flips that have been taken while executing the randomized algorithm. If you enumerated every possible such series of coin flips, you would see that at most a $2^{-n^2}$ fraction of them would lead the algorithm to conclude with the wrong answer.

  • $\begingroup$ That makes a lot more sense, thank you! Random string = random bits used by the algorithm. $\endgroup$
    Mar 22, 2021 at 1:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.