Lower bounds to randomized algorithms for graph properties

For any property P on n-vertex graphs, let C(P) be the minimum number of edges needed to be examined by any decision tree algorithm for determining P. In 1975 Rivest and Vuillemin settled the Aanderra-Rosenberg Conjecture, proving that C(P)=Ω(n²) for every nontrivial monotone graph property P. An intriguing open question is whether the theorem remains true when randomized algorithms are allowed. In this paper we show that Ω(n(log n) ^{1 12} edges need to be examined by any randomized algorithm for determining any nontrivial monotone graph property.