ylfink@water.UUCP (11/25/87)
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
THEORY OF COMPUTING SEMINAR
- Monday, November 30, 1987
Dr. Valerie King, of the University of California,
(8/7)
Berkeley, will speak on ``An Omega (n ) Lower Bound on
the Randomized Complexity of Graph Properties''.
TIME: 3:30 PM
ROOM: MC 6082
ABSTRACT
A decision tree algorithm determines whether an unknown
graph with n nodes has a property by examining the
entries of the graph's adjacency matrix and branching
according to the information already gained. All
(isomorphism-invariant) graph properties which are
monotone (not destroyed by the addition of edges) and
nontrivial (holds for some but not all graphs) have
2
been shown to require Omega (n ) queries in the worst case.
We investigate the power of randomness in recognizing
these properties by considering randomized decision
tree algorithms in which coins may be flipped to
determine the next entry to be examined. The
complexity of a randomized algorithm is the expected
number of entries that are examined in the worst case.
The randomized complexity of a property is the minimum
complexity of any randomized decision tree algorithm
which computes the property. We improve Yao's lower
bound on the randomized complexity of any monotone
(1/12)
nontrivial graph property from Omega (n(logn) ) to
(8/7)
Omega (n ).