next up previous contents
Next: Sensitive Functions Up: Boolean Functions Previous: Nondeterministic Decision Tree Complexity   Contents


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.


\begin{proof}
% latex2html id marker 2300We will prove that any nondeterminist...
...e queries are
required to compute $f$ in the bounded error setting.
\end{proof}

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.


next up previous contents
Next: Sensitive Functions Up: Boolean Functions Previous: Nondeterministic Decision Tree Complexity   Contents
Matthew Hayward Lower Query Bounds in the Quantum Oracle Model GitHub Repository