Answers are grounded in this paper and cite their sources.
In the Boolean decision tree model there is at least a linear gap between the Monte Carlo and the Las Vegas complexity of a function depending on the error probability. The author proves for a large class of read-once formulae that this trivial speed-up is the best that a Monte Carlo algorithm can achieve. For every formula F belonging to that class it is shown that the Monte Carlo complexity of F with two-sided error p is (1-2p)R(F), and with one-sided error p is (1-p)R(F), where R(F) denotes the Las Vegas complexity of F. The result follows from a general lower bound that is derived on the Monte Carlo complexity of these formulae.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
No takes yet. Share an insight, caveat, or question.
Miklós Sántha (2002) studied this question.
Synapse has enriched 2 closely related papers on similar clinical questions. Consider them for comparative context: