The Influence of Variables on Boolean Functions (Extended Abstract)

This paper applies methods from harmonic analysis to prove some general theorems on boolean functions. The result that is easiest to describe says that "Boolean functions always have small dominant sets of variables." The exact definitions will be given shortly, but let us be more specific: Let f be an n variable boolean function taking the value zero for half of the 2^n variable assignments. Then there is a set of o(n) variables such that almost surely the value of f is undetermined as long as these variables are not assigned values. This proves some of the conjectures made in [BL]. These new connections with..