Lower Bounds to Randominzed Algorithms for Graph Properties

Abstract:

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) = omega(n2) 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 omega(n(log n)1/12) edges need to be examined by any randomized algorithm for determining any nontrivial monotone graph property.