TY - GEN
T1 - LOWER BOUNDS TO RANDOMIZED ALGORITHMS FOR GRAPH PROPERTIES.
AU - Yao, Andrew Chi Chih
PY - 1987
Y1 - 1987
N2 - 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. R. Rivest and S. Vuillemin (1975) settled the Aanderra-Rosenberg Conjecture, proving that C(P) equals OMEGA (n**2) for every nontrivial monotone graph property P. An intriguing open question is whether the theorem remains true when randomized algorithms are allowed. The author reports progress on this problem, showing that OMEGA (n(log n)**1**/**1**2) edges must be examined by a randomized algorithm for determining any nontrivial monotone graph property.
AB - 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. R. Rivest and S. Vuillemin (1975) settled the Aanderra-Rosenberg Conjecture, proving that C(P) equals OMEGA (n**2) for every nontrivial monotone graph property P. An intriguing open question is whether the theorem remains true when randomized algorithms are allowed. The author reports progress on this problem, showing that OMEGA (n(log n)**1**/**1**2) edges must be examined by a randomized algorithm for determining any nontrivial monotone graph property.
UR - https://www.scopus.com/pages/publications/0023588496
U2 - 10.1109/sfcs.1987.39
DO - 10.1109/sfcs.1987.39
M3 - 会议稿件
AN - SCOPUS:0023588496
SN - 0818608072
SN - 9780818608070
T3 - Annual Symposium on Foundations of Computer Science (Proceedings)
SP - 393
EP - 400
BT - Annual Symposium on Foundations of Computer Science (Proceedings)
PB - IEEE
ER -