Journal: International Journal of Foundations of Computer Science
Authors: Richard Beigel and Anna Bernasconi
Abstract: We investigate the representation of Boolean functions as polynomials over the field GF(2), and prove an interesting characterization theorem: the degree of a Boolean function over GF(2) is equal to the size of its largest subfunction that takes the value 1 on an odd number of input strings. We then present some properties of odd functions, i.e., functions that take the value 1 on an odd number of strings, and analyze the connections between the problem of the existence of odd functions with very low maximal sensitivity and the long standing open problem of the relationship between the maximal sensitivity and the block sensitivity of Boolean functions.