Rivest-Vuillemin conjecture is true for monotone boolean functions with twelve variables
Research output: Journal Publications and Reviews (RGC: 21, 22, 62) › 21_Publication in refereed journal › peer-review
Author(s)
Related Research Unit(s)
Detail(s)
| Original language | English |
|---|---|
| Pages (from-to) | 19-34 |
| Journal / Publication | Discrete Mathematics |
| Volume | 253 |
| Issue number | 1-3 |
| Publication status | Published - 6 Jun 2002 |
Link(s)
Abstract
A Boolean function f(x1,x2,...,xn) is elusive if every decision tree computing / must examine all n variables in the worst case. It is a long-standing conjecture that every nontrivial monotone weakly symmetric Boolean function is elusive. In this paper, we prove this conjecture for Boolean functions with twelve variables. ©2002 Elsevier Science B.V. All rights reserved.
Research Area(s)
- Decision tree, Elusive, Monotone boolean function
Citation Format(s)
Rivest-Vuillemin conjecture is true for monotone boolean functions with twelve variables. / Gao, Sui-Xiang; Du, Ding-Zhu; Hun, Xiao-Dong; Jia, Xiaohua.
In: Discrete Mathematics, Vol. 253, No. 1-3, 06.06.2002, p. 19-34.Research output: Journal Publications and Reviews (RGC: 21, 22, 62) › 21_Publication in refereed journal › peer-review
