On the Monte carlo boolean decision tree complexity of read‐once formulae
Miklós Sántha · Random Structures and Algorithms · 1995
Abstract 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. We prove 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 formulaFbelonging to that class we show that the Monte Carlo complexity ofFwith two‐sided errorpis (1 − 2p)R(F), and with one‐sided errorpis (1 −p)R(F), whereR(F) denotes the Las Vegas complexity ofF. The result follows from a general lower bound that we derive on the Monte Carlo complexity of these formulae. This bound is analogous to the lower bound due to Saks and Wigderson on their Las Vegas complexity.