A Lemma for Proving Lower Query Bounds

The sensitivity of an input $x$ of a function $f$ is the number of Hamming neighbors $y$ of $x$ such that $f(x) \neq f(y)$. We will use the following lemma to establish lower bounds for functions based solely on their sensitivity for a particular input.

Lemma 2.2.1   Let $f$ be an $N$-bit Boolean function. If some input $x$ has $k$ Hamming neighbors $y$ such that $f(x) \neq f(y)$, then $\Omega(\sqrt{k})$ oracle queries are required to compute $f$ in the bounded error setting.

This lemma will not in general provide us with the best lower bound that can be attained from Ambainis' Theorem : we are maximizing $m/l$, but we make no attempt to maximize $m^{\prime}/l^{\prime}$. The strongest results of Ambainis' Theorem frequently arise from maximizing both. We will maximize both when dealing with partially symmetric functions in Theorem and graph connectivity in Theorem . The singleton class of functions described in Sections and is a class for which Lemma obtains optimal results.