Sensitive Functions

Nearly all the functions discussed so far have been evasive (or
conjectured to be so). In our final result we consider functions that
are not necessarily evasive. We call a Boolean function *f*
*sensitive* if for some input *x*, there are
(*N*(*f* )) Hamming
neighbors *y* of *x* such that
*f* (*x*) *f* (*y*). It is an open
question whether there are any nonsensitive functions.

Beals et al. proved () oracle queries are required to compute any Boolean function in the bounded error setting, but they suspect that this lower bound is not tight [2]. An open question is whether there are any functions which are not sensitive. If not, then () oracle queries are required to compute any Boolean function, which would be an improvement over what is currently known.