**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.