Influence-Based Independence

Conditional independence structures describe independencies of one set of variables from another set of variables conditioned upon a third set of variables. These structures are invaluable means for compact representations of knowledge because independencies can be exploited for useful factorizations. Conditional independence structures appear in different disguise in various areas of knowledge representation, be it the conditional independence of sets of random variables in probabilistic graphical models such as Bayesian networks or as conditional functions related to belief revision, or as in- dependencies induced by (embedded) multivalued dependencies in data bases. This paper investigates conditional independencies for Boolean functions using Fourier analysis. We define three notions of independence based on the notion of influence of a variable on a function and draw connections to multivalued dependencies.