Improved lower bounds on the randomized complexity of graph properties
We prove a lower bound of Omega(n(4/3) log(1/3) n) on the randomized decision tree complexity of any nontrivial monotone n-vertex graph property, and of any nontrivial monotone bipartite graph property with bipartitions of size it. This improves the previous best bound of Omega(n(4/3)) due to Hajnal (Combinatorica 11 (1991) 131-143). Our proof works by improving a graph packing lemma used in earlier work, and this improvement in turn stems from a novel probabilistic analysis. Graph packing being a well-studied subject in its own right, our improved packing lemma and the probabilistic technique used to prove it may be of independent interest. (c) 2007 Wiley Periodicals, Inc.
complexity graph properties decision trees graph packing randomized algorithms probabilistic method