An \(\Omega{} (n^{5/4})\) lower bound on the randomized complexity of graph properties (Q1180407)

Let \({\mathcal G}_ n\) be the set of labeled graphs on the vertex set \(V=\{1,2,\dots,n\}\). A graph property \(P\) is a subset of \({\mathcal G}_ n\) closed under isomorphism. A graph property \(P\) is monotone (increasing) if \(H\subset G\) and \(H\in P\) imply that \(G\in P\). A graph property \(P\) is nontrivial if \(P\neq \phi\) and \(P\neq {\mathcal G}_ n\). A decision tree algorithm \(A\) computes a graph property \(P\) for any input \(G\) by asking questions of the form ``Is the edge \((i,j)\) in \(G\)?'' The choice of questions depends only on the information gained so far. Let \({\mathcal A}_ P\) be the set of all decision tree algorithms for \(P\). Let \(\hbox{cost}(A,G)\) be the number of queries asked by \(A\) when \(G\) is the input. The randomized decision tree algorithm is a probability distribution \(\alpha\) over \({\mathcal A}_ P\). The expected number of queries asked by \(\alpha\) for input \(G\) is, \[ \hbox{cost}^ R(\alpha,G)=\sum_{A\in{\mathcal A}_ P}\alpha(A)\hbox{cost}(A,G). \] (Here we adopt the notation of \textit{P. Hajnal}: An \(\Omega(n^{4/3})\) lower bound on the randomized complexity of graph properties (see the review above). The randomized decision tree complexity \(R(P)\) of \(P\) is, by definition, \[ \min_{\alpha}\max_{G\in{\mathcal G}_ n}\hbox{cost}^ R(\alpha,G). \] It is proved that \(\Omega(n^{5/4})\) is a lower bound for the randomized decision tree complexity of any nontrivial monotone graph property \(P\). This result improves an earlier result obtained by \textit{A. Yao} in 1987. At the end of this paper the author remarks that \textit{P. Hajnal} has further reduced the lower bound for \(R(P)\) to \(\Omega(n^{4/3})\).