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 2.1.1: 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 2.5.1 and graph connectivity in Theorem 3.2.1. The singleton class of functions described in Sections 2.3 and 2.4 is a class for which Lemma 2.2.1 obtains optimal results.