The rivest-vuillemin conjecture on monotone boolean functions is true for ten variables

Sui-Xiang Gao; Weili Wu; Ding-Zhu Du; Xiao-Dong Hu

doi:10.1006/jcom.1999.0521

The rivest-vuillemin conjecture on monotone boolean functions is true for ten variables

Sui-Xiang Gao
, Weili Wu
, Ding-Zhu Du
, Xiao-Dong Hu

Department of Computer Science

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

3 Citations (Scopus)

Abstract

A Boolean function f(x₁, ..., 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. © 1999 Academic Press.

Original language	English
Pages (from-to)	526-536
Journal	Journal of Complexity
Volume	15
Issue number	4
DOIs	https://doi.org/10.1006/jcom.1999.0521
Publication status	Published - Dec 1999

Bibliographical note

Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

Funding

1 Supported in part by National Natural Science Foundation of China. 2 Supported in part by the National Science Foundation under Grant CCR-9530306.

Research Keywords

Decision trees

Access Output

10.1006/jcom.1999.0521Licence: Elsevier user license

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{879d0fd83ef4450d90010a9b80660d6e,

title = "The rivest-vuillemin conjecture on monotone boolean functions is true for ten variables",

abstract = "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. {\textcopyright} 1999 Academic Press.",

keywords = "Decision trees",

author = "Sui-Xiang Gao and Weili Wu and Ding-Zhu Du and Xiao-Dong Hu",

note = "Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].",

year = "1999",

month = dec,

doi = "10.1006/jcom.1999.0521",

language = "English",

volume = "15",

pages = "526--536",

journal = "Journal of Complexity",

issn = "0885-064X",

publisher = "Academic Press Inc.",

number = "4",

}

TY - JOUR

T1 - The rivest-vuillemin conjecture on monotone boolean functions is true for ten variables

AU - Gao, Sui-Xiang

AU - Wu, Weili

AU - Du, Ding-Zhu

AU - Hu, Xiao-Dong

N1 - Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

PY - 1999/12

Y1 - 1999/12

N2 - 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. © 1999 Academic Press.

AB - 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. © 1999 Academic Press.

KW - Decision trees

UR - https://www.scopus.com/pages/publications/0345884903

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-0345884903&origin=recordpage

U2 - 10.1006/jcom.1999.0521

DO - 10.1006/jcom.1999.0521

M3 - RGC 21 - Publication in refereed journal

SN - 0885-064X

VL - 15

SP - 526

EP - 536

JO - Journal of Complexity

JF - Journal of Complexity

IS - 4

ER -

The rivest-vuillemin conjecture on monotone boolean functions is true for ten variables

Abstract

Bibliographical note

Funding

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this