The Rivest–Vuillemin Conjecture on Monotone Boolean Functions Is True for Ten Variables

The full text article is not available for purchase.

The publisher only permits individual articles to be downloaded by subscribers.


A Boolean function f(x1, …, xn) 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. Copyright 1999 Academic Press.

Keywords: Boolean functions; decision trees; elusiveness

Document Type: Research Article

Affiliations: 1: Institute of Applied Mathematics, Chinese Academy of Sciences, Beijing, 100080, People's Republic of China 2: Department of Computer Science and Engineering, University of Minnesota, Minneapolis, Minnesota, 55455 3: Department of Computer Science, City University of Hong Kong, Kowloon Tong, Hong Kong, China

Publication date: December 1, 1999

Related content



Share Content

Access Key

Free Content
Free content
New Content
New content
Open Access Content
Open access content
Subscribed Content
Subscribed content
Free Trial Content
Free trial content
Cookie Policy
Cookie Policy
ingentaconnect website makes use of cookies so as to keep track of data that you have filled in. I am Happy with this Find out more