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 2.2.1. 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.