On the Monte carlo boolean decision tree complexity of read‐once formulae

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…