scientific article; zbMATH DE number 168429
Let \(C^ R(P)\) be the number of questions of the form `Does the graph \(G\) contain the edge \(e(i,j)\)?' that have to be asked in the worst case by any randomized decision tree algorithm for computing an \(n\)-vertex graph property \(P\). For non-trivial, monotone graph properties it is known that the deterministic complexity is \(\Omega(n^ 2)\) [see \textit{R. Rivest} and \textit{Vuillemin} , On recognizing graph properties from adjacency matrices, Theor. Comp. Sci. 3, 371-384 (1976; Zbl 0358.68079)]. The best uniform lower bound for all non-trivial, monotone graph properties is \(\Omega(n^{4/3})\) due to \textit{P. Hajnal} [Complexity of graph properties, An \(\Omega(n^{4/3})\) lower bound on the randomized complexity of graph properties. Combinatorica 11(2), 131-143 (1991; Zbl 0743.68076)]. No non-trivial, monotone graph property is known having a randomized complexity of less than \(n^ 2/4\). Some properties have been proven to have complexity of \(\Omega(n^ 2)\) [see \textit{A. Yao}, Probabilistic computation: towards a unified measure of complexity, Proc. 18th IEEE FOCS, 222-227 (1977)]. We refine the idea of Yao. This leads to a further improvement in the reductions of arbitrary graph properties to bipartite graph properties [see \textit{V. King}, Lower bounds on the complexity of graph properties, Proc. 20th ACM STOC, 468-476 (1988)] and yields a uniform lower bound for the subgraph isomorphism properties of \(\Omega(n^{3/2})\). Furthermore we show, that a large variety of isomorphism properties has as well as \(k\)-colourability require \(\Omega(n^ 2)\) questions.
- An asymptotic bound for the complexity of monotone graph properties
- A lower bound for the complexity of monotone graph properties
- The monotone complexity of \(k\)-clique on random graphs
- Lower bounds to randomized algorithms for graph properties
- Improved lower bounds on the randomized complexity of graph properties
- Improved lower bounds on the randomized complexity of graph properties
- Bounded monochromatic components for random graphs
- On the typical structure of graphs in a monotone property
- scientific article; zbMATH DE number 4204394
- The monoid of the random graph
- An \(\Omega{} (n^{5/4})\) lower bound on the randomized complexity of graph properties
- The monoid of the random graph
- Bounded monochromatic components for random graphs
- No easy puzzles: hardness results for jigsaw puzzles
- Improved lower bounds on the randomized complexity of graph properties
- Computing graph properties by randomized subcube partitions
- Improved lower bounds on the randomized complexity of graph properties
- Monotone Properties of k -Uniform Hypergraphs Are Weakly Evasive
- Measures on monotone properties of graphs
- On the typical structure of graphs in a monotone property
- Lower bounds to randomized algorithms for graph properties
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4036171)