A monotone Boolean function is called fair if it outputs 1 on exactly half of its inputs. In this note, we prove that the single variable function f(x) = x{sub}1 has the minimum correlation with the majority function over all fair monotone Boolean functions, which was conjectured by Blum, Burch and Langford (FOCS '98). Moreover we show a weak learning algorithm for monotone Boolean functions with respect to the uniform distribution and investigate the performance of the algorithm.
展开▼
