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.
Gao, Sui-xiang; Du, Ding-Zhu; Hu, Xiao-dong; Jia, Xiaohua.
Rivest-Vuillemin Conjecture Is True for Monotone Boolean Functions with Twelve Variables.
Retrieved from the University of Minnesota Digital Conservancy,
Content distributed via the University of Minnesota's Digital Conservancy may be subject to additional license and use restrictions applied by the depositor.