Citation
Sx. Gao et al., Nontrivial monotone weakly symmetric Boolean functions with six variables are elusive, THEOR COMP, 223(1-2), 1999, pp. 193-197
Citations number
7
Categorie Soggetti
Computer Science & Engineering
Journal title
THEORETICAL COMPUTER SCIENCE
ISSN journal
03043975
→ ACNP
Volume
223
Issue
1-2
Year of publication
1999
Pages
193 - 197
Database
ISI
SICI code
0304-3975(19990728)223:1-2<193:NMWSBF>2.0.ZU;2-6
Abstract
A Boolean function f(x(1),...,x(n)) is elusive if every decision tree evalu
ating f must examine all n variables in the worst case. Rivest and Vuillemi
n conjectured that every nontrivial monotone weakly symmetric Boolean funct
ion is elusive, In this note, we show that this conjecture is true for n =
6. (C) 1999 Elsevier Science B.V. All rights reserved.