Motivation Why randomness? Faster. Simpler. Price:a nonzero error probability Usually can be controlled to arbitrarily small. Repeating k times drops the error probability to c-k for some constant c>1. Second part of the lecture. 3Motivation ◼ Why randomness? ❑ Faster. ❑ Simpler. ◼ Price: a nonzero error probability ❑ Usually can be controlled to arbitrarily small. ❑ Repeating 𝑘 times drops the error probability to 𝑐 −𝑘 for some constant 𝑐 > 1. ◼ Second part of the lecture. 3