Valerie King

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-87-364
July 1987

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1987/CSD-87-364.pdf

A decision tree algorithm determines whether an input 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 graph properties which are monotone (not destroyed by the addition of edges) and nontrivial (holds for some but not all graphs) have been shown to require Omega( n^2) queries in the worst case.

In this paper, 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 nontrivial graph property from Omega(n log^1/12n) to Omega(n^8/7).

BibTeX citation:

@techreport{King:CSD-87-364,
    Author = {King, Valerie},
    Title = {An Omega(n^8/7) Lower Bound on the Randomized Complexity of Graph Properties},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1987},
    Month = {Jul},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1987/5476.html},
    Number = {UCB/CSD-87-364},
    Abstract = {A decision tree algorithm determines whether an input graph with <i>n</i> nodes has a property by examining the entries of the graph's adjacency matrix and branching according to the information already gained. All graph properties which are monotone (not destroyed by the addition of edges) and nontrivial (holds for some but not all graphs) have been shown to require Omega(<i>n</i>^2) queries in the worst case. <p>In this paper, 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 nontrivial graph property from Omega(<i>n</i> log^1/12<i>n</i>) to Omega(<i>n</i>^8/7).}
}

EndNote citation:

%0 Report
%A King, Valerie
%T An Omega(n^8/7) Lower Bound on the Randomized Complexity of Graph Properties
%I EECS Department, University of California, Berkeley
%D 1987
%@ UCB/CSD-87-364
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1987/5476.html
%F King:CSD-87-364