Lower bounds to randomized algorithms for graph properties
- 1 October 1987
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 393-400
- https://doi.org/10.1109/sfcs.1987.39
Abstract
For any property P on n-vertex graphs, let C(P) be the minimum number of edges that need 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) = Ω(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 report progress on this problem, showing that Ω(n(log n)1/12) edges must be examined by a randomized algorithm for determining any nontrivial monotone graph property.Keywords
This publication has 7 references indexed in Scilit:
- Probabilistic Boolean decision trees and the complexity of evaluating game treesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1986
- Lower bounds on probabilistic linear decision treesTheoretical Computer Science, 1985
- The complexity of problems on probabilistic, nondeterministic, and alternating decision treesJournal of the ACM, 1985
- Probabilistic computations: Toward a unified measure of complexityPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1977
- On recognizing graph properties from adjacency matricesTheoretical Computer Science, 1976
- Determining graph properties from matrix representationsPublished by Association for Computing Machinery (ACM) ,1974
- On the time required to recognize properties of graphsACM SIGACT News, 1973