MIT
22
An improvement [KS]
lWhen k
vertices, error probability 2/k
»big when k small
lIdea: once k small, change algorithm
»algorithm needs to be
safer
»but can afford to be
slower
lAmplify by
repetition!
»Repeat base algorithm
many times