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   () 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() algorithm to compute the OR of N bits, this lower bound is asymptotically tight.

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