Browsing by Author "Gao, Sui-xiang"

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    Rivest-Vuillemin Conjecture Is True for Monotone Boolean Functions with Twelve Variables
    (2000-10-02) Gao, Sui-xiang; Du, Ding-Zhu; Hu, Xiao-dong; Jia, Xiaohua
    A Boolean function f(x1, x2, …, xn) is elusive if every decision tree computing f must examine all n variables in the worst case. It is a long-standing conjecture that every non-trivial monotone weakly symmetric Boolean function is elusive. In this paper, we prove this conjecture for Boolean functions with twelve variables.