On Learning Monotone Boolean Functions Under the Uniform Distribution

Abstract

In this paper, we prove two general theorems on monotone Boolean functions which are useful for constructing an learning algorithm for monotone Boolean functions under the uniform distribution. A monotone Boolean function is called fair if it takes the value 1 on exactly half of its inputs. The first result proved in this paper is that the single variable function f ( x ) = x_ i has the minimum correlation with the majority function among all fair monotone functions (Theorem 1). This proves the conjecture by Blum, Burch and Langford (FOCS ’98) and improves the performance guarantee of the best known learning algorithm for monotone Boolean functions under the uniform distribution proposed by them. Our second result is on the relationship between the influences and the average sensitivity of a monotone Boolean function. The influence of variable x_ i on f is defined as the probability that f ( x ) differs from f ( x ⊕. e _ i ) where x is chosen uniformly from 0, 1^n and x ⊕e_ i means x with its i -th bit flipped. The average sensitivity of f is defined as the sum of the influences over all variables x_ i . We prove that a somewhat unintuitive result which says if the influence of every variable on a monotone Boolean function is small, i.e., O (1/ n n ^c) for some constant c τ; 0, then the average sensitivity of the function must be large, i.e., ω(log n ) (Theorem 11). We also discuss how to apply this result to construct a new learning algorithm for monotone Boolean functions.