An (n^5/4) lower bound on the randomized complexity of graph properties
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})\).
- An \(\Omega{} (n^{4/3})\) lower bound on the randomized complexity of graph properties
- Lower bounds to randomized algorithms for graph properties
- scientific article; zbMATH DE number 1754599
- Improved lower bounds on the randomized complexity of graph properties
- scientific article; zbMATH DE number 168429
- Lower bounds for the size of random maximal H-free graphs
- A lower bound for the complexity of monotone graph properties
- scientific article; zbMATH DE number 1775407
- An asymptotic bound for the complexity of monotone graph properties
- On a certain complexity estimate in graph theory
- An \(\Omega{} (n^{4/3})\) lower bound on the randomized complexity of graph properties
- Improved lower bounds on the randomized complexity of graph properties
- scientific article; zbMATH DE number 2019628 (Why is no real title available?)
- scientific article; zbMATH DE number 1754599 (Why is no real title available?)
- Edge and pair queries-random graphs and complexity
- Searching for an edge in a graph
- The critical complexity of graph properties
- Lower bounds to randomized algorithms for graph properties
- A lower bound for the recognition of digraph properties
This page was built for publication: An \(\Omega{} (n^{5/4})\) lower bound on the randomized complexity of graph properties
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1180407)
