Evaluation, strength, and relevance of variables of boolean functions

Peter L. Hammer, Alexander Kogan, Uriel G. Rothblum

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

Abstract

Given a Boolean function f, we define the importance of a set S of variables by an expression measuring to what extent the variables in S determine the value of f. This "evaluation" uses a "constancy" measure which is assumed to be a real-valued convex function defined on [0, 1]. In spite of the generality of the constancy measure, it is shown that any such evaluation is in strong agreement with the classical concept of the Winder-strength of variables of a monotone Boolean function. Further, we study a special class of evaluations called relevances, characterize completely the cases of extreme relevance value, relating the sets of maximum relevance to fictitious (dummy) variables and support sets, and establish a lower bound on the relevance of sets "containing" implicants or implicates of a Boolean function.

Original languageEnglish (US)
Pages (from-to)302-312
Number of pages11
JournalSIAM Journal on Discrete Mathematics
Volume13
Issue number3
DOIs
StatePublished - 2000

ASJC Scopus subject areas

  • Mathematics(all)

Keywords

  • Boolean function
  • Convex constancy measure
  • Influence of variables
  • Majorization
  • Support set
  • Winder preorder

Fingerprint

Dive into the research topics of 'Evaluation, strength, and relevance of variables of boolean functions'. Together they form a unique fingerprint.

Cite this