Name
Title | ||
|---|---|---|
The Rivest-Vuillemin conjecture on monotone Boolean functions is true for ten variables |
Abstract | ||
|---|---|---|
A Boolean function f ( x 1 , …, x n ) 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 =10. |
Year | DOI | Venue |
|---|---|---|
1999 | 10.1006/jcom.1999.0521 | J. Complexity |
Keywords | DocType | Volume |
elusiveness,monotone Boolean function,Rivest-Vuillemin conjecture,Boolean functions,decision trees | Journal | 15 |
Issue | ISSN | Citations |
4 | Journal of Complexity | 2 |
PageRank | References | Authors |
0.53 | 5 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Suixiang Gao | 1 | 44 | 12.48 |
| Weili Wu | 2 | 2093 | 170.29 |
| Ding-Zhu Du | 3 | 3497 | 283.06 |
| Xiaodong Hu | 4 | 628 | 47.63 |