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 $\Omega(N(f))$ Hamming neighbors $y$ of $x$ such that $f(x) \neq f(y)$. It is an open question whether there are any nonsensitive functions.

Theorem 4.4.1   $O(\sqrt[4]{D(f)})$ oracle queries are required to compute any sensitive function $f$ in the bounded error setting.

Beals et al. proved $\Omega(\sqrt[6]{D(f)})$ 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 $\Omega(\sqrt[4]{D(f)})$ oracle queries are required to compute any Boolean function, which would be an improvement over what is currently known.