Nondeterministically Evasive Functions

With an understanding of decision tree complexity we can now prove a lower bound on a class of evasive functions. In analogy to evasive functions whose deterministic decision tree complexity is $N$ we call functions with nondeterministic decision tree complexity $N$ Nondeterministically evasive. Every nondeterministically evasive functions is evasive.

Theorem 4.3.1   $\Omega(\sqrt{N})$ oracle queries are required to compute any nondeterministically evasive $N$-bit Boolean function in the bounded error setting.

This proof establishes that nondeterministically evasive functions have inputs that are sensitive to negation on at least half of their bits; the result then follows from Lemma . Not all evasive functions are nondeterministically evasive. OR is an example of a nondeterministically evasive function; since Beals et al. provide an $O(\sqrt{N})$ algorithm to compute the OR of $N$ bits, this lower bound is asymptotically tight.