Rivest-Vuillemin conjecture is true for monotone boolean functions with twelve variables

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)19-34
Journal / PublicationDiscrete Mathematics
Volume253
Issue number1-3
Publication statusPublished - 6 Jun 2002

Abstract

A Boolean function f(x1,x2,...,xn) is elusive if every decision tree computing / must examine all n variables in the worst case. It is a long-standing conjecture that every nontrivial monotone weakly symmetric Boolean function is elusive. In this paper, we prove this conjecture for Boolean functions with twelve variables. ©2002 Elsevier Science B.V. All rights reserved.

Research Area(s)

  • Decision tree, Elusive, Monotone boolean function

Citation Format(s)

Rivest-Vuillemin conjecture is true for monotone boolean functions with twelve variables. / Gao, Sui-Xiang; Du, Ding-Zhu; Hun, Xiao-Dong; Jia, Xiaohua.

In: Discrete Mathematics, Vol. 253, No. 1-3, 06.06.2002, p. 19-34.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review