Citation
Sx. Gao et al., The Rivest-Vuillemin conjecture on monotone Boolean functions is true for ten variables, J COMPLEX, 15(4), 1999, pp. 526-536
Citations number
10
Categorie Soggetti
Engineering Mathematics
Journal title
JOURNAL OF COMPLEXITY
ISSN journal
0885064X
→ ACNP
Volume
15
Issue
4
Year of publication
1999
Pages
526 - 536
Database
ISI
SICI code
0885-064X(199912)15:4<526:TRCOMB>2.0.ZU;2-P
Abstract
A Boolean Function f(x(1), ..., x(n)) is elusive if every decision tree eva
luating f must examine all n variables in the worst case. Rivest and Vuille
min conjectured that every nontrivial monotone weakly symmetric Boolean fun
ction is elusive. In this note, we show that this conjecture is true for n
= 10. (C) 1999 Academic Press.