# Independent iterations in Las Vegas algorithms

In [Randomized Algorithms, Motwani and Raghavan] book, it is stated that the method of independent iterations to reduce the error probability in Monte Carlo algorithms (amplification according to Wikipedia) has its analogy in Las vegas algorithms. The authors then cited the following references:

1. Alt, Helmut, et al. "A method for obtaining randomized algorithms with small tail probabilities." Algorithmica 16.4 (1996): 543-547.
2. Luby, Michael, Alistair Sinclair, and David Zuckerman. "Optimal speedup of Las Vegas algorithms." Information Processing Letters 47.4 (1993): 173-180.

These suggestions of the mentioned papers are a bet very generalized in my opinion. I am wondering - are there well-known algorithms that use the concepts introduced in the previous papers ?

Rapid restarts in SAT solving are one area where the sequence introduced in Luby,Sinclair,Zuckerman is used. See for example Section 2.1 in http://www.st.ewi.tudelft.nl/~marijn/publications/rapid.pdf for some references.

• Restart strategies are used in CSP solvers too. CSP is more general than SAT. Despite the Luby sequence being nice theoretically, other sequences are also used in practice. – Juho Nov 21 '12 at 0:13