On Decision Tree Complexity of Boolean Function and Yao's Question
Received:October 19, 1999  
Key Word: Boolean function   decision tree   complexity   Rivest-Vuillemin conjecture.  
Fund ProjectL:Supported by the National Natural Science Foundation of China (10171095), Foundation of Chinese Academy of Science (J2001), and Foundation of GSCAS(yzjj200105)
Author NameAffiliation
GAO Sui-xiang Math. Dept.
Graduate School of the Chinese Academy of Sciences
Hua Look-Keng Inst. of Appl. Math
& Info. Sci.
Beijing
China 
YANG De-zhuang Math. Dept.
Graduate School of the Chinese Academy of Sciences
Hua Look-Keng Inst. of Appl. Math
& Info. Sci.
Beijing
China 
Hits: 1535
Download times: 879
Abstract:
      A Boolean function f(x1,x2,…,xn) is said to be elusive, if every decision tree algorithm computing f must examine all n variables in the worst case. In 1988, A.C.C. Yao introduced a question: Is any nontrivial monotone Boolean function that is invariant under the transitive act of group Cm×Cn elusive? The positive answer to this question supports the famous Rivest-Vuillemin conjecture on decision tree complexity. In this paper, we shall partly answer this question.
Citation:
DOI:10.3770/j.issn:1000-341X.2002.04.005
View Full Text  View/Add Comment  Download reader