✦ LIBER ✦

Nontrivial monotone weakly symmetric Boolean functions with six variables are elusive

✍ Scribed by Gao Sui-Xiang; Hu Xiao-Dong; Wu Weili

Book ID: 104326656
Publisher: Elsevier Science
Year: 1999
Tongue: English
Weight: 268 KB
Volume: 223
Category: Article
ISSN: 0304-3975
DOI: 10.1016/s0304-3975(98)00350-8

No coin nor oath required. For personal study only.

✦ Synopsis

A Boolean function _/+I,. . ,x,,) is elusive if every decision tree evaluating f must examine all n variables in the worst case. Rivest and Vuillemin conjectured that every nontrivial monotone weakly symmetric Boolean function is elusive. In this note, we show that this conjecture is true for n = 6.