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 ?


1 Answer 1


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.

  • $\begingroup$ 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. $\endgroup$
    – Juho
    Nov 21, 2012 at 0:13

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.